BOJ 2204 - 도비의 난독증 테스트

문제

N개의 단어 중 대소문자를 무시하고 사전순으로 가장 앞선 단어를 원래 형태로 출력하라.

입력

여러 테스트 케이스가 주어지며, 각 케이스의 첫 줄에 N, 이후 N개의 단어가 주어진다. 0이면 종료.

출력

각 케이스마다 사전순으로 가장 앞선 단어를 출력한다.

예제

입력	출력
`3` `Cat` `fat` `bAt` `4` `call` `ball` `All` `aLL` `0`	`bAt` `All`

풀이

소문자로 변환한 키와 원본을 HashMap에 매핑하고, 소문자 배열을 정렬하여 첫 번째 원본을 출력한다.

각 단어를 소문자로 변환한 것을 키, 원본을 값으로 HashMap에 저장한다
소문자 배열을 사전순 정렬한다
정렬된 첫 번째 키에 대응하는 원본 단어를 출력한다

핵심 아이디어: 대소문자 무시 비교를 위해 소문자로 변환 후 정렬하되, 출력은 원본 형태를 유지한다.

코드

package day749;
 
import java.util.*;
 
public class Day731BOJ2204난독증 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();
    HashMap<String, String> hashMap = new HashMap<>();
    while (true) {
      int n = sc.nextInt();
      if (n == 0)
        break;
      String[] str = new String[n];
      for (int i = 0; i < n; i++) {
        str[i] = sc.next();
      }
      for (int i = 0; i < n; i++) {
        String temp = str[i].toLowerCase();
        hashMap.put(temp, str[i]);
        str[i] = str[i].toLowerCase();
      }
      Arrays.sort(str);
      sb.append(hashMap.get(str[0])).append("\n");
    }
    System.out.println(sb);
    sc.close();
  }
}

복잡도

시간: O(N log N)
공간: O(N)

문제