C++ 백준 BOJ 1620 나는야 포켓몬 마스터 이다솜

 

 

 

 

포켓몬 이름을 입력받아 입력 순서대로 번호를 부여하고 도감을 만듭니다.

해당하는 포켓몬의 이름을 입력하면 번호를, 번호를 입력하면 이름을 출력하는 문제입니다.

 

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

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
 
int main() {
	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
 
	int N, M;
	string p;
	string name[100001];
	unordered_map <string,int> pocketmon;
 
	cin >> N >> M;
	for(int i=1; i <= N; i++){ // 각 포켓몬 이름을 받아 
		cin >> p;
		name[i] = p; // 배열 name 에 저장
		pocketmon.insert(make_pair(p, i)); // 해시맵 pocketmon에 저장
	}
	
	for(int i=0; i < M; i++){
		string input;
		cin >> input;
        	auto item = pocketmon.find(input);
     
		if(item!=pocketmon.end()){ // 이름을 입력하면 map 참조
				 cout << item->second << "\n";
			}
		else{ // 번호를 입력하면 배열 참조
			int a = stoi(input);
			cout << name[a] << "\n";
		}
	}
	
	return 0;
}

 

풀이

그냥 배열을 만들어서 탐색을 하는 방법이 있지만, 최대인 100,000개의 입력이 있을 경우 무조건 시간초과입니다.

 

 

따라서 포켓몬의 번호를 검색하는 경우는 배열 인덱스로 접근하면 되고,

포켓몬의 이름을 검색하는 경우는 해시맵 을 사용합니다.

 

 

 

해시맵  (std::unordered_map) 이란?

기존의 이진탐색트리 기반 C++의 STL컨테이너인 std::map 에서 정렬이 불필요한 경우를 위해 만들어졌고,

map보다 더 빠른 탐색을 하기 위한 자료구조입니다.

 

std::map과 달리 이진 탐색트리가 아닌 해시 테이블로 구현된 컨테이너 입니다.

중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보입니다.

 

std::unordered_map은 요소를 자동으로 정렬하지 않으며 요소의 검색, 삽입, 삭제 연산이 평균적으로 상수 시간에 가능합니다.

참고자료

[Data Structure] unordered_map 사용법