BOJ 1620 나는야 포켓몬 마스터

문제 링크

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

시간, 공간 제한

시간 : 2초

공간 : 256MB

문제 접근 방향

- key와 value 값을 저장하고 해당 자료구조를 탐색하여 적절한 값을 찾는 문제

- 단순히 배열을 자료구조로 선택할 경우 인덱스접근은 O(1)이지만 string을 찾기 위해서는 선형 탐색시 O(n)이된다.

- 입력 최대 값이 100,000이고 선형 탐색을 통한 문제 해결시 전체 시간 복잡도는 O(n^2)으로 시간초과 발생한다.

- string을 찾기 위해 O(logn)정도의 탐색 시간 복잡도가 필요하고 해당 시간 복잡도를 가진  map 자료 구조를 사용한다.

- map은 key, value 한쌍을 저장할 수 있는 자료 구조이고 내부는 레드블랙트리라는 균형 이진 트리로 구현이 되어있기 때문에
  탐색 시간이 O(logn)이다.

 

#include <iostream>
#include <map>
#include <string>

using namespace std;

map<string, int> d1;
string d2[100005];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	string name;
	for (int i = 1; i <= n; ++i)
	{
		cin >> name;
		d1.insert({name, i});
		d2[i] = name;
	}
	string q;
	for (int i = 0; i < m; ++i)
	{
		cin >> q;
		if (atoi(q.c_str()) == 0)
			cout << d1[q] << '\n';
		else
			cout << d2[atoi(q.c_str())] << '\n';
	}
	return(0);
}