[Baekjoon Online Judge] 1620. 나는야 포켓몬 마스터 이다솜

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

 

핵심

N, M은 최대 100,000이다.

 

배열의 인덱스는 숫자이기 때문에

포켓몬 번호가 주어졌을 때 포켓몬 이름을 찾는 것은 배열로 가능하지만

포켓몬 이름이 주어졌을 때 포켓몬 번호를 찾는 것은 배열로 불가능하다.

그렇다고 일일이 배열을 탐색하면 O(N)의 탐색을 N번 수행하므로 O(N^2)의 시간복잡도가 된다. (시간 초과)

 

따라서 String으로 O(1)에 탐색이 가능하면서 Key, Value 형태로 데이터를 저장하여 대응하는 포켓몬 번호까지 쉽게 가져올 수 있는 해시 맵을 사용할 것이다.

 

Code (Java)

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

public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        String[] pokedex = new String[N + 1];
        Map<String, Integer> map = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            String pokemon = br.readLine();
            pokedex[i] = pokemon;
            map.put(pokemon, i);
        }

        for (int i = 0; i < M; i++) {
            String str = br.readLine();
            if (isNumeric(str)) {
                sb.append(pokedex[Integer.parseInt(str)]);
            } else {
                sb.append(map.get(str));
            }
            sb.append('\n');
        }

        System.out.println(sb);
    }

    public static boolean isNumeric(String str) {
        return str != null && !str.isEmpty() && str.matches("[0-9]+");
    }
}