오답노트 #1620 : 나는야 포켓몬 마스터 이다솜

풀이방법 및 문제점

2022.03.27

번호를 입력받았다면 포켓몬 이름을 출력하고,

포켓몬 이름을 출력받았다면 번호를 출력해야 한다.

두 가지 기준으로 빠르게 자료를 찾아와야 하는 문제이다.

 

결론부터 말하자면 HashMap<String, Integer> 하나와 String[] 하나를 사용하면 된다.

 

이를 알아내기까지 두 번의 시행착오를 거쳤다.

 

먼저, 한 개의 HashMap만 사용해보았다.

시간초과가 발생한다.

Key를 이용해 Value를 찾는 것은 빠르게 해낼 수 있지만

Value를 이용해 Key를 찾고자 할 경우엔 반복문을 사용해야 하기 때문이다.

시간복잡도가 제곱으로 불어난다.

 

그래서 다음으로는, 두 개의  HashMap을 사용해보았다.

HashMap<Integer, String>

HashMap<String, Integer>

동일한 데이터셋을 Key와 Value의 순서만 바꾸어 저장한 두 개의 HashSet을 만들어둔 뒤, 입력받은 값에 따라 두 HashMap 중 하나를 참조한 것이다.

한 개의 HashMap을 사용했을 때보다는 빨랐지만 여전히 시간초과가 발생했다.

 

해결방법은 간단했다.

바로 String[]을 사용하는 것이었다.

String[] 배열 또한 주어진 Integer 값에 맞는 특정 String 값을 빠르게 찾아올 수 있는 자료구조이다.

해시맵은

HashMap<String, Integer>

이렇게 하나만 사용하면 되었다.

HashMap<Integer, String>보다 String[] 이 훨씬 간단한 자료구조라서 자료를 넣고 찾아오는 데 자원이 덜 드는 것 같다.

 

속도의 차이는 있었지만 세 방법 모두 올바른 결과값 출력에는 문제가 없었다.

 

정답 게시물 바로가기

 

코드

Java(2022.03.27, HashMap 하나를 사용)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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> hm = new HashMap<Integer, String>();
		
		for(int i = 0; i<n; i++) {
			hm.put(i+1, br.readLine());
		}
		
		for(int i = 0; i<m; i++) {
			String input = br.readLine();
			if(hm.containsValue(input)) {
				//주어진 데이터가 포켓몬의 이름인 경우
				for(Map.Entry<Integer, String> entry : hm.entrySet()) {
					if(entry.getValue().equals(input)) System.out.println(entry.getKey());
				}
			}else {
				//주어진 데이터가 포켓몬의 번호인 경우
				System.out.println(hm.get(Integer.parseInt(input)));
			}
		}
	}

}

Java(2022.03.27, HashMap 두 개를 사용)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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> hm1 = new HashMap<Integer, String>();
		HashMap<String, Integer> hm2 = new HashMap<String, Integer>();
		
		for(int i = 0; i<n; i++) {
			String temp = br.readLine();
			hm1.put(i+1, temp);
			hm2.put(temp, i+1);
		}
		
		for(int i = 0; i<m; i++) {
			String input = br.readLine();
			if(hm1.containsValue(input)) {
				//주어진 데이터가 포켓몬의 이름인 경우
				System.out.println(hm2.get(input));
			}else {
				//주어진 데이터가 포켓몬의 번호인 경우
				System.out.println(hm1.get(Integer.parseInt(input)));
			}
		}
	}

}