1620번: 나는야 포켓몬 마스터 이다솜

문제

포켓몬 도감에 수록된 포켓몬의 이름이 주어질 때, 번호를 입력받으면 이름을, 이름을 입력받으면 번호를 출력하는 문제입니다.

• 입력: 첫째 줄에 포켓몬의 개수 N과 맞춰야 하는 문제의 개수 M이 주어집니다. 둘째 줄부터 N개의 줄에 포켓몬의 이름이 1번부터 N번까지 차례대로 주어집니다. 이어서 M개의 줄에 맞춰야 하는 문제가 번호 또는 이름으로 주어집니다.
• 출력: 입력으로 번호가 들어오면 해당하는 포켓몬의 이름을, 이름이 들어오면 해당하는 포켓몬의 번호를 출력합니다.

링크: https://www.acmicpc.net/problem/1620

풀이

입력되는 쿼리의 종류가 숫자(번호)와 문자열(이름) 두 가지이므로, 양방향 검색이 모두 O(1)의 시간 복잡도로 빠르게 이루어져야 시간 초과를 방지할 수 있습니다. 번호로 이름을 찾을 때는 문자열 배열(String Array)을 사용하고, 이름으로 번호를 찾을 때는 해시 맵(Hash Map)을 사용하는 것이 메모리와 속도 측면에서 가장 효율적입니다.

1. 자료구조 초기화: 인덱스로 바로 접근할 수 있는 크기 N + 1의 문자열 배열 arr과, 이름을 키로 번호를 값으로 가지는 해시 맵 map을 선언합니다.
2. 도감 저장: 1번부터 N번까지 포켓몬의 이름을 입력받으며, 배열의 해당 인덱스에 이름을 저장하고 동시에 해시 맵에도 (이름, 번호) 쌍을 저장합니다.
3. 질의(Query) 처리: 입력받은 문자열의 첫 글자가 숫자인지 알파벳인지 검사(s.charAt(0) >= '0' && s.charAt(0) <= '9')합니다. 숫자라면 정수형으로 변환하여 배열 arr에서 이름을 찾고, 문자열이라면 그대로 맵 map에서 번호를 찾아 출력합니다.

코드

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));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int n = Integer.parseInt(st.nextToken());
       int m = Integer.parseInt(st.nextToken());

       // 번호로 이름을 찾는 용도 (빠른 인덱스 접근)
       String[] arr = new String[n + 1];
       // 이름으로 번호를 찾는 용도
       Map<String, Integer> map = new HashMap<>();

       for (int i = 1; i <= n; i++) {
          String s = br.readLine();
          arr[i] = s;
          map.put(s, i);
       }

       while (m-- > 0) {
          String s = br.readLine();
          
          // 첫 글자가 숫자라면 번호로 판단하여 배열에서 이름 검색
          if (s.charAt(0) >= '0' && s.charAt(0) <= '9') {
             bw.write(arr[Integer.parseInt(s)] + "\n");
          } 
          // 알파벳이라면 이름으로 판단하여 맵에서 번호 검색
          else {
             bw.write(map.get(s) + "\n");
          }
       }

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

알고리즘 분류

자료구조 (Data Structure), 해시를 사용한 집합과 맵 (Hash Map)