[백준] 1620번: 나는야 포켓몬 마스터 이다솜 [C++]

 

알고리즘 분류: 자료 구조, 해시를 사용한 집합과 맵

문제 링크: https://www.acmicpc.net/problem/1620

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

 

 

【 풀이 】

 

17219번: 비밀번호 찾기와 같이 map을 이용하여 풀 수 있는 문제이다.

2023.05.11 - [백준 [BAEKJOON]] - [백준] 17219번: 비밀번호 찾기 [C++]

[백준] 17219번: 비밀번호 찾기 [C++]

단, value로도 key를 찾을 수 있는지를 묻는 문제이다.

key를 이용하여 value를 찾는 것은 인덱스, 메서드, 함수 등을 활용해 쉽게 구할 수 있다.

그러나 value로 key를 찾으려면 map을 모두 돌아보면서 직접 구현하는 수밖에 없지만,

이는 시간복잡도가 O(n)이고 이 문제에서는 시간 초과를 유발하게 된다.

따라서 인덱스가 key로 저장된 맵과 포켓몬 이름이 key로 저장된 맵 두 개를 선언하고

각각의 경우에 인덱스값을 호출해주면 된다.

 

【 코드 】

 

#include<iostream>
#include<string>
#include<map>
using namespace std;

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

	map<int, string>info;
	map<string, int>info2;
	string id;

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		cin >> id;
		info.insert({ i, id });
		info2.insert({ id, i });
	}
	for (int i = 1; i <= m; i++)
	{
		string s;
		cin >> s;
		if (s[0] <= 57 && s[0] >= 48)
			cout << info[stoi(s)] << '\n';
		else
			cout << info2[s] << '\n';
	}
	return 0;
}