백준 1620번 - 나는야 포켓몬 마스터 이다솜

https://www.acmicpc.net/problem/1620

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

 

풀이과정

 입력이 100,000이기 때문에 탐색이 아닌 map을 이용했다. map({key, value})에서 key를 이용해 value를 찾을 때, map이 트리 형태이기 때문에 시간 복잡도 O(longN)을 가지고, unordered_map은 O(1)의 시간 복잡도를 가진다. 정렬이 필요하지 않기 때문에 unordered_map을 사용했고, 양방향 탐색을 요구했지만 map에서는 양방향 탐색이 불가능하다. 따라서 두 가지 값이 모두 key가 될 수 있도록 map을 2개 만들고 입력값에 따라 map에서 검색하여 결과를 출력했다.

 

느낀점

 일반 탐색, map, unordered_map의 시간 복잡도를 체감해볼 수 있는 문제였다. 특히, map을 2개 만들어 양방향 탐색이 가능하도록 하는 것이 포인트인 것 같다.

 

<unordered_map과 map의 시간 차이>

 

 

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;

unordered_map<string, string> mp1, mp2;
int n, m;
string temp;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> temp;
		string it = to_string(i);
		mp1.insert({ it, temp});
		mp2.insert({ temp, it });
	}

	for (int i = 0; i < m; i++) {
		cin >> temp;
		if (!isalpha(temp[0])) cout << mp1[temp] << "\n";
		else cout << mp2[temp] << "\n";
	}

	return 0;
}