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

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

 

1. 개요

N개의 input 값이 주어지고, M개의 문제에서 숫자가 주어지면 해당 인덱스에 해당하는 포켓몬 이름을, 포켓몬 이름이 주어지면 해당 인덱스(포켓몬 번호)를 출력하는 문제였다.

 

✔️ 숫자 -> 포켓몬 이름 출력

✔️ 문자열(포켓몬 이름) -> 해당하는 포켓몬 번호 출력

 

N : 도감에 수록된 포켓몬의 개수 (1 <= N <= 100,000)

M : 문제의 개수 (1 <= M <= 100,000)

 

 

2. 걸린 시간 : 20분

 

 

3. 사용한 자료 구조 : HashMap, Array

 

 

4. 아이디어

✔️ N개의 input 값을 String 배열, HashMap 두 군데 모두 저장

 

why❓

N개의 데이터를 리스트 한 군데에만 저장 시,

문제가 포켓몬 이름으로 나오는 경우엔, 무조건 indexOf() 메서드를 사용해야 한다.

그렇게 되면 최악의 경우 매 문제마다 N 만큼 탐색해야 할 수도 있다. => 그럼 무조건 시간초과가 난다!

 

따라서 주어진 문제의 종류에 따라 아래와 같이 경우를 나눴다.

 

i) 문제가 숫자인 경우

String 배열로 포켓몬 이름을 찾는다.

 

ii) 문제가 포켓몬 이름인 경우

Key가 String(포켓몬이름)인 HashMap을 이용하여 숫자(포켓몬 번호)를 찾는다.

** HashMap으로 찾는 경우 시간 복잡도가 O(1)이기 때문에 검색 시간을 줄일 수 있다.

 

 ✔️ 문제의 숫자, 알파벳 판단 방법

- 문제의 첫 글자를 charAt(0)-'0'을 한다.

- 숫자인 경우, 0~9의 값이 나올 것이다.

- 따라서, 9보다 큰 경우 알파벳으로 판단하였다.

 

 

5. 헷갈렸던 점

문제에서 "또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 아참! 일부 포켓몬은 마지막 문자만 대문자일 수도 있어. " 이런 문장이 있었다.

 

이 부분을 읽고 포켓몬 이름과 문제에서 주어지는 포켓몬 이름의 대소문자 구분을 하지 않아야 한다는 것인가 헷갈렸다.

그니까 N개의 입력 중 "Abc"라는 포켓몬이 주어지고, 문제로 "abC" 이렇게 주어졌을 때 두 포켓몬을 같은 포켓몬으로 봐야 하는 것인지 

아님 "Abc", "abC" 이렇게 첫 글자와 마지막 글자가 대문자 인 경우만 허용하고 "aBc"는 허용하지 않는다는 것인지 헷갈렸다.

 

근데 그냥 무시하고 input 그대로 받았는데 통과했다.

저 문장은 아직도 이해가 안된다...

 

 

6. Solution Code

아래 코드에 문제가 있다면 언제든지 댓글 달아주시면 감사합니다:)

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

public class Main {

	static int N, M;
	static String[] arr;
	static HashMap<String, Integer> hashmap;

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

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

		arr = new String[N + 1]; // 각 인덱스에 해당하는 포켓몬 이름 저장
		hashmap = new HashMap<>(); // 포켓몬 이름에 해당하는 인덱스 저장

		for (int i = 1; i <= N; i++) {
			arr[i] = br.readLine();
			hashmap.put(arr[i], i);
		}

		for (int i = 0; i < M; i++) {

			String now = br.readLine();

			// now가 문자인 경우
			if (now.charAt(0) - '0' > 9) {
				sb.append(hashmap.get(now)).append("\n");
			}
			// now가 숫자인 경우
			else {
				int idx = Integer.parseInt(now);
				sb.append(arr[idx]).append("\n");
			}
		} // end for i

		System.out.println(sb.toString());
	}

}