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

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

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

문제만 읽어봐도 Hash를 이용한 Map형태로 접근하면 된다는 것을 확인할 수 있던 문제

초기 하나의 HashMap만을 이용하여 구현을 할려 했으나, 시간 초과로 인해 2개의 HashMap 을 사용해서 문제를 풀었습니다.

오답코드 (시간 초과)

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

public class Main2 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        HashMap<String, String> poketMon = new HashMap<>();

        for (int i = 1; i <= N; i++) {
            String name = br.readLine();
            poketMon.put(Integer.toString(i), name);
        }

        StringBuilder sb = new StringBuilder();
        while (M-- > 0) {
            String findStr = br.readLine();
            if (poketMon.containsKey(findStr)) {
                sb.append(poketMon.get(findStr));
            } else {
                for (String poketNum : poketMon.keySet()) {
                    if (poketMon.get(poketNum).equals(findStr)) {
                        sb.append(poketNum);
                    }
                }
            }

            sb.append('\n');
        }

        System.out.println(sb);
    }

}

문제 풀이

• HashMap의 인자로는 <String, String>을 주었습니다. 찾아야하는 포켓몬 번호 혹은 이름을 받았을때 별도로 캐스팅없이 진행하기 위해 두개다 String으로 작성했습니다.
• 받은 인자값이 containsKey로 존재한다면 몬스터 이름이 아닌 포켓몬 넘버를 받은 것이니 get을 이용해 포켓몬 이름을 sb에 입력합니다.
• 받은 인자값이 containsKey로 존재하지 않는다면 몬스터 이름으로 받은것이니 keySet으로 맵을 포켓몬 이름과 같은 인덱스 값이 나올때가지 순회하여 포켓몬 넘버를 sb에 입력합니다.

오답 풀이

• 100,000 개의 데이터를 처리해야하다 보니 일반적인 O(n) 으로 for문을 돌릴 경우 시간초과가 일어난듯 보입니다.

정답 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        HashMap<Integer, String> poketMonNum = new HashMap<>();
        HashMap<String, Integer> poketMonStr = new HashMap<>();

        for (int i = 1; i <= N; i++) {
            String name = br.readLine();
            poketMonNum.put(i, name);
            poketMonStr.put(name, i);
        }

        StringBuilder sb = new StringBuilder();
        while (M-- > 0) {
            String findStr = br.readLine();
            if (isStrNum(findStr)) {
                sb.append(poketMonNum.get(Integer.parseInt(findStr)));
            } else {
                sb.append(poketMonStr.get(findStr));
            }

            sb.append('\n');
        }

        System.out.println(sb);
    }

    private static boolean isStrNum(String findStr) {
        try {
            Integer.parseInt(findStr);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }

}

문제 풀이

• <포켓몬 넘버, 포켓몬 이름>, <포켓몬 이름, 포켓몬 넘버> 형태의 2개의 HashMap을 선언하였습니다.
• 만일 입력받은 값이 숫자이면 poketMonNum에서 숫자가 아닐 경우 poketMonStr에서 get을 이용해 데이터를 가져오는 방식입니다.
• 숫자인지 아닌지에 대한 코드는 상당많습니다. 그중 try / catch 를 이용한 방식의 코드가 개인적으로 마음에 들어 사용했습니다.

추가적인 isStrNum 코드

private static boolean isStrNum(String findStr) {
    for (int i = 0; i < findStr.length(); i++) {
        if (!Character.isDigit(findStr.charAt(i))) {
            return false;
        }
    }
    return true;
}

private static boolean isStrNum(String findStr) {
        for (int i = 0; i < findStr.length(); i++) {
            if (49 <= findStr.charAt(i) && findStr.charAt(i) <= 57) {
                continue;
            } else {
                return false;
            }
        }
        return true;
    }