[백준] 1181번_단어 정렬(Java)

문제 풀이

백준의 1181번 문제입니다. 문제 출처

(1) 문제 파악

알파벳 소문자로 이루어진 단어를 정렬하는 문제입니다.

(2) 문제 풀이 방법 생각하기

중복된 단어는 하나만 남기고 제거해야 한다고 하니, Set을 사용하면 좋을 것 같네요!

Set에 단어들을 담아 중복을 제거한 뒤, 단어들을 문제의 정렬 방식대로 정렬하면 됩니다.

(3) 시간 복잡도 확인

시간 제한은 2초 입니다. 즉, 대략 2억번 연산 안에 문제를 해결해야 합니다.

Collections.sort()의 시간 복잡도는 O(nlogn)입니다.

compareTo()의 시간 복잡도는 최악의 경우 문자열의 최대 길이(m)에 따라 달라질 수 있습니다. (시간 복잡도 O(m))

결과적으로는 O(mnlogn) 이 나옵니다. 이때,

\[1 <= m <= 50\] \[1 <= n <= 20,000\]

이므로 가능한 범위 내에 있습니다.

(4) 구현

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        Set<String> set = new HashSet<>();
        for(int i=0; i<N; i++) {
            set.add(br.readLine());
        }

        List<String> list = new ArrayList<>(set);
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                if(s1.length() == s2.length())  return s1.compareTo(s2);
                return s1.length() - s2.length();
            }
        });

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(String s: list) {
            bw.write(s + "\n");
        }

        bw.flush();
        br.close();
        bw.close();
    }
}