[BOJ] 1181: 단어 정렬(JAVA)

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

예제 입력 1

13

but

i

wont

hesitate

no

more

no

more

it

cannot

wait

im

yours

예제 출력 1 

i

im

it

no

but

more

wait

wont

yours

cannot

hesitate

 

---

[문제 풀이]

 

1. Hashmap map<Integer, ArrayList<String>>에 <문자열 길이, 해당 길이 문자열 arraylist>를 저장한다. 

   만약 입력이 i wont more 이라면, key = 1인 경우 value ArrayList에는 "i" 존재, key=4인 경우, value arraylist에는 "wont", "more"이 존재하게 될 것이다.

 

2. ArrayList<Integer> key에는 키 값만 저장할 것이다. 나중에 이를 오름차순으로 정렬하여 짧은 길이의 문자열부터 출력할 수 있도록 할 것이다. arraylist에 중복된 값은 넣으면 안되므로 !key.contains(len) 을 이용하여 해당 arraylist에 유일한 값들만 저장하도록 한다.

 

3. Collections.sort(key)를 이용하여 arraylist key를 정렬한다. 

 

4. arraylist key의 원소를 이용해 map key의 작은 값부터 탐색한다.

    4-1. 만약 map의 value인 arraylist의 크기가 1보다 크다면 같은 길이의 문자열이 2개 이상 존재하는 것을 의미한다. 따라서 사전 순 정렬이 필요하므로 Collections.sort()를 이용해 해당 길이의 문자열들이 들어있는 arraylist를 사전 순 정렬하여 출력한다. 

    4-2. map value arraylist의 크기가 1이라면 해당 길이의 문자열이 하나 존재하는 것이므로 별다른 정렬없이 출력하면 된다.

 

[코드]

import java.util.*;

public class Main {

    public static void main(String[] args) {
    
      Scanner sc = new Scanner(System.in);
      int N = sc.nextInt();
      HashMap<Integer, ArrayList<String>> map = new HashMap<>();
      ArrayList<Integer> key = new ArrayList<>();
      for(int i=0;i<N;i++) {
          String str = sc.next();
          int len = str.length();
           if(!key.contains(len))
               key.add(len);
       
           ArrayList<String> al = new ArrayList<>();
           if(map.containsKey(len)) {
               al = map.get(len);
               if(!al.contains(str)) {
                   al.add(str);
                  map.put(len,al);
               }

           }
           else {
               al.add(str);
              map.put(len, al);
          
           }
      }
      
      Collections.sort(key);
      
      for(int i=0;i<key.size();i++) {
       	ArrayList<String> al = map.get(key.get(i));
       	if(al.size()>1) {
           Collections.sort(al);
       	}
      	for(int j=0;j<al.size();j++)
          System.out.println(al.get(j));
      }
   }
}