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

문제 url:
나는야 포켓몬 마스터 이다솜

문제:

🤔 문제 알아보기

---

지문이 너무 길어서, 살짝 당황했던 문제이다. 포켓몬 안봐유
문제를 같이 살펴보면,
첫 줄에 N과 M을 받는데, N은 몬스터 도감의 개수이며 M은 찾고자하는 몬스터 이름 혹은 번호 개수를 입력받는다.

그래서 만약, 번호를 입력하면 번호에 해당하는 몬스터 이름을, 몬스터 이름을 입력하면 해당 몬스터의 번호를 출력하는 문제이다.

몬스터 마다 고유 번호가 쥐어주는 문제면 우리는 쉽게 Map 자료구조를 생각할 수 있다.

Map이란?
key-value pair로 이루어진 자료구조로, key를 통해 value를 매핑할 수 있다.
즉, 비유하자면 금고 같은 것이다.
금고 키를 넣으면 금고에 고유한 물건을 넣거나 가져올 수 있는?

그럼 코드를 살펴보겠다.

🐱‍👤 실제 코드

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sbd = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        HashMap<String, String> Monster_book = new HashMap<>();
        HashMap<String, String> Monster_book_num = new HashMap<>();

        for(int i = 1; i <= N; i++) {
            String word = br.readLine();
            Monster_book.put(word, String.valueOf(i));
            Monster_book_num.put(String.valueOf(i), word);
        }

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

            if(Monster_book.containsKey(word)) {
                sbd.append(Monster_book.get(word)).append("\n");

            } else {
                sbd.append(Monster_book_num.get(word)).append("\n");
            }
        }
        System.out.println(sbd);
    }
}

특별히 어려운 로직은 없다.

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

            if(Monster_book.containsKey(word)) {
                sbd.append(Monster_book.get(word)).append("\n");

            } else {
                sbd.append(Monster_book_num.get(word)).append("\n");
            }
        }

여기서 Monster_book(몬스터 이름이 키인 map)에 입력된 값이 키로 존재하면 해당 HashMap에서 get()메서드로 value를 불러와 StringBuilder에 넣고,

그렇지 않으면 Monster_book_num(인덱스 번호가 키인 map)에서 인덱스 번호를 넣어 value를 불러오는 과정이다.

그렇다면! 왜 Monster_book 과 Monster_book_num 두 개의 Map이 존재해야 하는가?

그 이유는 숫자를 통한 이름 불러오기 때문이다.

🤢 트러블 슈팅

---

회고에 적을 내용이었으나, 여기에 같이 적어보겠다.
HashMap은 키-값 쌍으로 이루어진 자료구조로 key를 통해 value를 찾을 수 있다.
하지만, value를 통해 key를 알아내려면 완전탐색을 해야한다.
로직을 짜본다면 아래와 같이 이중 for문으로 나타낼 수 있다.

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

            if(Monster_book.containsKey(word)) {
                sbd.append(Monster_book.get(word)).append("\n");

            } else {
                for (Sring val : Monster_book.keySet()) {
                	if(Monster_book.get(val).equals(word)) {
                    sbd.append(Monster_book.get(word)).append("\n");
                   }
                }
            }
        }

그렇다면 왜 완전탐색이 안되는지 살펴보면
이번 문제의 시간 제한은 2초이며, N과 M은 각각 100,000의 수 까지 가질 수 있다.
즉, 시간 복잡도는 O(N ^ 2)이 될 수 있는데, 총 10,000,000,000(100억)번의 연산 횟수가 나올 수 있기 때문에 할 수 없는 방식이다.

또한 필자는 ArrayList를 생각하여, 번호는 인덱스를 문자열은 indexOf() 메서드를 사용해 생각해보았다.

하지만, 해당 부분 역시 indexOf()도 O(N)의 시간 복잡도를 가지는 부분과 만약 문자열을 넣었는데, 찾지 못하면 -1을 반환하기 때문에 NoSuchElement 런타임 에러를 발생시킬 수 있다.

😊 코드 리팩토링

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sbd = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        HashMap<String, String> Monster_book = new HashMap<>();
        String[] Monster_book_num = new String[N+1];

        for(int i = 1; i <= N; i++) {
            String word = br.readLine();
            Monster_book.put(word, String.valueOf(i));
            Monster_book_num[i] = word;
        }

        for(int i = 0; i < M; i++) {
            String word = br.readLine();
            char isNum = word.charAt(0);
            if(isNum >= 65) { //즉 문자라면
                sbd.append(Monster_book.get(word)).append("\n");

            } else { // 숫자 아스키 코드는 48(0) ~ 57(9)까지 이므로
                sbd.append(Monster_book_num[Integer.parseInt(word)]).append("\n");
            }
        }
        System.out.println(sbd);
    }

}

사실 첫 번째, 코드는 먼저 HashMap을 두 개를 쓰기 때문에 메모리가 많이 든다.
그래서 인덱스로 값을 불러올 수 있으며 메모리가 Map보다 효율적인 배열을 사용해서 인덱스를 이용해 값을 불러오고자 한다.

또한 아래 코드를 보면 charAt을 이용한 부분이 있는데,

			char isNum = word.charAt(0);
            if(isNum >= 65) { //즉 문자라면
                sbd.append(Monster_book.get(word)).append("\n");

            } else { // 숫자 아스키 코드는 48(0) ~ 57(9)까지 이므로
                sbd.append(Monster_book_num[Integer.parseInt(word)]).append("\n");
            }

이는, 첫 번째 단어가 아스키 코드로 65('A')보다 크다면 문자이기 때문에 아래의 코드를 그렇지 않은 것은 숫자이기 때문에 배열에서 인덱스 값으로 넣어 찾을 수 있다.

리팩토링 코드 - 528ms
이전 코드 - 560ms

배열로 리팩토링을 하고나니 메모리와 시간도 효율적으로 구할 수 있다.