[백준 1620] 나는야 포켓몬 마스터 이다솜

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

 

---

1. 아이디어

 

문제의 서론이 너무 길어서 처음에 다소 문제를 이해하기 어려웠으나, 본질적인 문제는 'N만큼 포켓몬을 입력받은 후 M개의 문제의 답을 출력하라' 였다. 여기서 입력하는 포켓몬은 String 이였고, M개의 문제는 (포켓몬 이름 or 도감번호) 둘 중 하나인데, (포켓몬이름 -> 도감 번호 출력) / (도감 번호 -> 포켓몬이름 출력) 두가지 형태로 출력하는 것이다.

 

문제를 이해하자마자 HashMap이 생각이 났다. 이 문제또한 일반적인 for문을 사용하여 탐색하면 시간초과가 날 것이 뻔했기 때문에 HashMap을 사용하여 탐색을 용이하게 하기 위함이였다. 그러나, 아래 코드를 보면 문제가 발생했다. key : 포켓몬, value : 도감번호로 hashmap에 저장했더니 key값을 이용해 value를 찾을 때는 문제가 없는데, 반대로 Value 값으로 Key값을 찾으려 하니 entrySet() 사용으로 반복문을 이용한 순회가 불가피한 것이었다.

 

우선 혹시 모르니 제출해보았지만, 역시나 시간초과가 발생했다.

// [백준_1620] 나는야 포켓몬 마스터 이다솜
public class B_1620 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N(포켓몬 개수), M(문제 개수) 입력
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // key : 포켓몬, value : 도감번호
        HashMap<String, Integer> map = new HashMap<>();

        // 포켓몬 입력
        for(int i=1; i<=N; i++){
            String pokemon = br.readLine();
            map.put(pokemon, i);
        }

        // 풀어야 할 문제 (입력 : 포켓몬 -> 도감번호 / 도감번호 -> 포켓몬)
        for(int i=0; i<M; i++){
            String prob = br.readLine();
            if(prob.charAt(0) >= '0' && prob.charAt(0) <= '9') {
                int do_num = Integer.parseInt(prob);
                // HashMap에서 Value로 Key값 접근 위함
                for(HashMap.Entry<String, Integer> entry : map.entrySet()){
                    if(entry.getValue() == do_num){
                        System.out.println(entry.getKey());
                    }
                }
            }
            else {
                System.out.println(map.get(prob));
            }
        }
    }
}

 

해결 방법은 생각보다 단순했다. HashMap 하나가 아닌, (도감번호 -> 포켓몬) 접근용 배열을 하나 더 생성하여 숫자가 입력되면 이 배열의 인덱스로 접근하면 불필요한 순회없이 두 탐색 모두 실행시간을 최소화 할 수 있었다.

 

2. 코드

package IntStudy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

// [백준_1620] 나는야 포켓몬 마스터 이다솜
public class B_1620 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N(포켓몬 개수), M(문제 개수) 입력
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // key : 포켓몬, value : 도감번호
        HashMap<String, Integer> map = new HashMap<>();
        // 도감번호 -> 포켓몬 접근용 배열
        String[] arr = new String[N+1];


        // 포켓몬 입력
        for(int i=1; i<=N; i++){
            String pokemon = br.readLine();
            map.put(pokemon, i);
            arr[i] = pokemon;
        }

        // 풀어야 할 문제 (입력 : 포켓몬 -> 도감번호 / 도감번호 -> 포켓몬)
        for(int i=0; i<M; i++){
            String prob = br.readLine();
            if(prob.charAt(0) >= '0' && prob.charAt(0) <= '9') {
                int do_num = Integer.parseInt(prob);
                System.out.println(arr[do_num]);
            }
            else {
                System.out.println(map.get(prob));
            }
        }
    }
}