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

생각

1번부터 N번까지의 포켓몬의 이름을 입력으로 받고 M개의 포켓몬의 정보를 통해 해당 포켓몬의 이름이나 번호를 출력하는게 문제입니다. N과 M이 100000이하의 자연수이고 포켓몬의 이름이 최대 20이기 때문에 일반적인 반복문을 통해 포켓몬의 정보를 찾으려면 N*M*20 대략 2천억번의 연산이 필요합니다. 

따라서 O(1)의 시간복잡도를 가진 해쉬맵을 사용하여 문제를 풀었습니다.

 

우선 포켓몬의 이름을 Key, 번호를 Value를 가진 해쉬맵을 만들고 반대로 번호를 Key, 포켓몬의 이름을 Value로 가진 해쉬맵을 만들었습니다.

다음으로 포켓몬의 번호가 입력으로 들어왔을때 문자열이 숫자인지를 판별한다음 포켓몬의 번호를 Key로 가진 해쉬맵에서 포켓몬의 이름을 출력하도록 했습니다. 반대의 경우에도 동일한 로직으로 풀었습니다.

 

(처음엔 포켓몬의 이름을 Key, 번호를 Value로 선언한 해쉬맵에 포켓몬의 정보를 모두 넣었습니다. 포켓몬의 숫자가 들어왔을때 해쉬맵의 Key 정보들을 가진 keySet()을 통해 Value로 Key를 찾는 함수를 만들어 탐색하도록 하였는데 시간초과가 난것을 확인하고 해쉬맵을 하나 더 추가했습니다!)

Java code

package com.java.algorithm;

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

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

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		String[] init = br.readLine().split(" ");
		int N = Integer.parseInt(init[0]); //전체 포켓몬개수
		int M = Integer.parseInt(init[1]); // 문제개수
		
		HashMap<String,Integer> StringMap = new HashMap<>(); // 문자열이 키인 해쉬맵
		HashMap<Integer,String> DigitMap = new HashMap<>(); // 숫자가 키인 해쉬맵
		
		for (int i = 1; i <= N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String s = st.nextToken();
			StringMap.put(s, i);			
		}
		for (String k : StringMap.keySet()) {
			int value = StringMap.get(k);
			DigitMap.put(value, k);
		}
		
		
		for (int i = 1; i <= M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String temp = st.nextToken();
			//숫자인지 판별
			if(isNumber(temp)) {
				sb.append(DigitMap.get(Integer.parseInt(temp))).append("\n");
				
			}else {
				sb.append(StringMap.get(temp)).append("\n");
			}
		}
		System.out.print(sb);


	}
	private static boolean isNumber(String s) {
		for (int i = 0; i < s.length(); i++) {
			if(!Character.isDigit(s.charAt(i))) return false;
		}
		return true;
	}
	//hashmap에서 value로 key찾기
//	private static String getKey(Map<String,Integer> map, Integer value) {
//		for (String key : map.keySet()) {
//			if(map.get(key).equals(value)) {
//				return key;
//			}
//		}
//		return null;
//		
//	}
	
	

}