문제 출처

단계별로 풀어보기 > 집합과 맵 > 나는야 포켓몬 마스터 이다솜
https://www.acmicpc.net/problem/1620

문제 설명

포켓몬 도감에 수록되어있는 포켓몬 개수 N과 맞춰야 하는 문제의 개수 M이 주어진다. 이 때, 1<= N,M <= 100,000이다.
수록된 포켓몬 개수 N개는 전부 알파벳(첫글자 대문자, 나머지 문자 소문자, 일부는 마지막도 대문자)로 주어진다.
이 후, 맞춰야하는 문제의 개수 M개는 숫자와 포켓몬 이름 중 랜덤으로 주어진다.
문제에 따른 정답을 출력하라.

접근 방법

조건에 따라서 찾아야하는 값이 다르므로, HashMap을 2개 생성한다. 이 때, 하나는 포켓몬 이름으로 받을 수 있게 <String,Integer> 형태, 다른 하나는 <Integer,String> 형태로 생성한다.
각각 주어진 포켓몬에 따라서 입력하고, 문제가 주어지면 해당 문제가 포켓몬의 이름인가 도감 번호인가 판단하기 위해서 문제의 첫글자가 아스키 코드 값 49 ~ 57사이면 숫자이므로 <Integer,String> 형태의 HashMap에서 꺼내오고 아닌 경우 <Stirng,Integer> 형태의 HashMap에서 꺼내온다.

import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;
public class 나는야_포켓몬_마스터_이다솜 {

    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());

        HashMap<String, Integer> hm1 = new HashMap<>();
        HashMap<Integer, String> hm2 = new HashMap<>();

        int count = 1;

        for(int i = 0; i < N; i++){
            String pocketmon = br.readLine();
            hm1.put(pocketmon,count);
            hm2.put(count++,pocketmon);
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < M; i++){
            String pc = br.readLine();

            if(49 <= pc.charAt(0) && pc.charAt(0) <= 57){
                sb.append(hm2.get(Integer.parseInt(pc))).append(" ").append("\n");
            } else{
                sb.append(hm1.get(pc)).append(" ").append("\n");
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

처음 풀이할 때는, 하나의 HashMap에 저장하고, 거기서 문제를 맞출 때, try catch문을 통해서 문자인지 숫자인지 판별하여 숫자인경우 key를 전부 순회하여 value가 맞을 때까지 진행했지만, 이는 시간 복잡도가 결국 O(M^2)이 되어서 최대 100,000 x 100,000 으로 2초안에 해결하지 못한다.

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class 나는야_포켓몬_마스터_이다솜_review {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Map<String, Integer> hm = new HashMap<>();

        int count = 1;

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        for(int i = 0; i < N; i++){
            String Pocketmon = br.readLine();
            hm.put(Pocketmon,count++);
        }

        StringBuilder sb = new StringBuilder();

        for(int j = 0; j < M; j++){
            String pm = br.readLine();
            try{
                int n = Integer.parseInt(pm);
                for(String key : hm.keySet()){
                    if(hm.get(key) == n) sb.append(key).append(" ").append("\n");
                }
            }catch (NumberFormatException e){
                sb.append(hm.get(pm)).append(" ").append("\n");
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

문제푼 흔적