[코딩테스트 챌린지] 백준 2204 도비의 난독증 테스트

문제

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

문제 탐색하기

 

1. 문제 유형 파악하기

해당 문제는 문자열을 오름차순으로 정렬한 뒤 그 문자열을 출력하면 되는 문제입니다.
java의 정렬 알고리즘은 여러가지가 있지만 문자열을 정렬해야하기에 사용하기 간단한 Collections.sort() 를 사용하도록 하겠습니다.

2. 정렬 설계하기

문자열을 모두 소문자 또는 대문자로 치환하면 어떤 문자열이 사전순으로 젤 앞쪽에 위치하는지는 빠르게 구할 수 있습니다. 하지만 여기서 고려해야할 부분은 다시 그 문자열의 원래 형태를 알아야한다는 것입니다.

따라서 처음에 문자열을 입력받을때 HashMap을 사용하여 입력받은 문자열을 소문자로 치환하여 키로 저장하고 본래의 문자열을 value로 저장합니다.

Collections.sort를 사용해서 hashmap의 keyset을 정렬한다면 해당 키로 손쉽게 기존 문자열을 얻어올 수 있을 것입니다.

3. 시간복잡도 파악하기

Collections.sort() 의 시간복잡도는 O(nlogn) 입니다.
n은 최대 1000까지 주어질 수 있으며 테스트 케이스의 개수는 0이 입력되면 끝이기때문에 T로 생각할 수 있습니다. 따라서 시간 내에는 충분히 가능한 시간복잡도 입니다.

코드 설계하기

1. 0이 입력되면 반복을 끝내기 위해 while문을 설계합니디.
2. 입력값을 저장할 HashMap을 선언합니다. key에는 문자열을 소문자로 치환한 값을 넣어주고 value 값에는 문자열 그대로를 넣어줍니다.
3. map의 keyset을 ArrayList에 저장합니다.
4. map의 키값을 저장한 list를 Comparator를 사용해서 문자열 오름차순으로 정렬해줍니다.
5. list의 첫번째 데이터를 가져와서 map에서 찾아줍니다.
6. 결과값을 저장해서 테스트케이스가 모두 종료되면 출력해줍니다.

 

정답 코드

package backjun;

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

public class Dobi {

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

        int n = Integer.parseInt(reader.readLine());
        List<String> result = new ArrayList<>();

        while(n != 0){

            Map<String, String> map = new HashMap<>();

            for(int i=0; i<n; i++){
                String str = reader.readLine();
                map.put(str.toLowerCase(), str);
            }

            List<String> keySet = new ArrayList<>(map.keySet());

            keySet.sort(new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o1.compareTo(o2);
                }
            });

            result.add(map.get(keySet.get(0)));
            n = Integer.parseInt(reader.readLine());
        }

        for(String str : result){
            System.out.println(str);
        }


    }
}