백준 1181번 단어 정렬

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class SortWord {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<String> strings = new ArrayList<>();
//        int delcount = 0;
//        for (int i = 0; i < N; i++) {
//            String str = br.readLine();
//            strings.add(str);
//            for (int j = 0; j < i-delcount; j++) {
//                if(str.equals(strings.get(j))){
//                    strings.remove(j);
//                    delcount++;
//                    break;
//                }
//            }
//        }
        Set<String> seenStrings = new HashSet<>(); // 중복을 검사하기 위한 HashSet
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            if (!seenStrings.contains(str)) {
                strings.add(str);
                seenStrings.add(str);
            }
        }
        
        Collections.sort(strings);
        Collections.sort(strings, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return Integer.compare(s1.length(),s2.length());
            }
        });
        for(String s : strings){
            System.out.println(s);
        }
    }
}

문제조건

1. 중복된 문자열 제거
2. 문자열 길이가 작은 순으로 정렬
3. 그런 문자열이 많다면, 문자열 사전 순으로 정렬

풀이방법

1. • 주석 풀이
     문자열을 하나씩 입력받고, list에 저장한다.
     list를 다시 돌며 해당 문자열이 있는지 확인하고 있다면 삭제한다(contains메서드와 동일한 동작)
2. • 본 풀이
     중복제거를 위한 hashset을 만들고, hashset에 있는 문자열이 아니라면, hashset과 list 둘다 문자열을 추가한다.
     (list를 다시 돌며 확인할 필요없이 중복이 제거된 hashset을 통해 비교해준다.) -> 시간복잡도 측면에서 훨씬 효율적이다.

3. 문제 조건중, 2번조건을 수행하고, 3번조건을 수행한다면, 결국 3번 조건으로만 정렬이 되버린다.
   따라서 3번조건을 먼저 Collections.sort()로 오름차순 정렬하고,
   길이를 비교하는 2번조건을 수행한다.

4. Comparator 메서드로 길이에 대한 오름차순 정렬을 수행한다.

후기

중복제거 방법, 사전식 정렬, 길이별 정렬
자주 나오는 유형들을 한 문제에서 접할 수 있는 아주 좋은 문제인것 같다.
특히 hashset을 통한 중복제거 방식이 인상깊었다.