[코딩테스트 챌린지] 백준 1181 단어 정렬 (java)

문제

 

문제 탐색하기

1. 정렬 조건 확인하기

문제를 잘 읽어보면 조건이 3가지임을 알 수 있었습니다. 

1. 중복된 단어 제거
2. 단어의 길이 오름차순
3. 단어의 길이가 같을 경우 사전 순 정렬

중복된 단어가 input 값으로 주어지면 제거 해줘야 한다는 것과 단어의 길이 및 단어로 정렬하는 다중 정렬 조건이 있다는 것을 알 수 있습니다.

 

2. HashSet으로 중복된 단어 제거하기

List로 입력을 받게되면 중복값을 없애기 위해 순회하는 로직이 들어가야하고 map을 사용하게 되면 불필요하게 value값을 세팅해줘야하는 것은 아닌지 고민이 되었습니다.

중복된 값을 제거해주는 Collection은 Set 입니다. 따라서 input 값을 저장할때 HashSet을 활용하면 전체 input 값 중에 중복된 단어가 제거되어 첫번째 정렬 조건을 만족시킬 수 있습니다.

 

3. HashSet 정렬 시키기

HashSet을 정렬시키기 위해서는 여러 방법이 있지만 저는 stream().sorted() 를 활용해서 원하는 조건을 적용시키려 합니다.

시간복잡도에 대해 얘기해보자면 먼저 stream 은 HashSet 요소에 대한 Iterator를 생성하는 단계로써 시간 복잡도는 O(1)과 같다고 합니다. 

sorted는 HashSet의 요소들을 Comparator에 따라 정렬하는 단계입니다. 정렬 알고리즘으로써 시간 복잡도는 O(nlog(n)) 입니다. 

마지막으로 정렬시킨 set을 출력시켜줘야 하는데 이때 요소들을 전체적으로 순회할 것이라 시간 복잡도는 O(n) 입니다.

가장 지배적인 복잡도는 O(nlog(n))임을 알 수 있었고 단어는 최대 2만개까지 주어질 수 있으므로 주어진 시간 내에 탐색이 가능할 것으로 생각됩니다.

 

코드 설계하기

1. 단어의 개수 세팅
2. 입력받는 단어 중 중복을 제거하기 위해 HashSet에 데이터 저장
3. set.stream().sorted 를 통해 정렬 방식을 오버라이드해서 구현
   1. 단어의 길이 오름차순
   2. 단어의 길이가 같을 경우 단어 사전 순
4. HashSet 출력

 

시도 회차 수정 사항

1회차) HashSet을 활용하고 싶었지만 정렬을 구현함에 어려움을 느껴 HashSet 정렬에 대해 찾아보던 중 stream().sorted를 알 수 있게 되었습니다.

 

2회차) 정렬한 Set을 List에 담아서 그 List를 출력하려했는데 너무 불필요한 로직이 아닐까 생각이 들었습니다. 알고보니 정렬시킨 set을 바로 출력할 수 있다는 것을 알 수 있어서 다시 문제풀이를 진행했습니다.

 

정답 코드

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

public class SortWords {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        // 1. 단어의 개수 N을 세팅
        int count = Integer.parseInt(reader.readLine());

        HashSet<String> set = new HashSet<>();
        for(int i=0; i<count; i++){
            String str = reader.readLine();
            // 2. 입력받는 단어 중 중복단어를 제거하기 위해 HashSet에 단어 추가
            set.add(str);
        }

        // 3. HashSet 정렬 구현
        set.stream().sorted(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                // 3-2. 단어의 길이가 같으면 오름차순
                if(o1.length() == o2.length()){
                    return o1.compareTo(o2);
                    // 3-1. 단어의 길이로 오름차순
                }else if(o1.length() > o2.length()){
                    return 1;
                }else{
                    return -1;
                }
            }
        }).forEach(System.out::println); // 4. 정렬된 HashSet 을 순회하며 출력

    }
}