[백준][자료 구조] 1620 나는야 포켓몬 마스터 이다솜 c++구현

목차

 

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

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

문제

 

문제 구현 방향

탐색 시간을 줄이기 위해서 string-int형식은 시간 복잡도가 O(logN)이 나오는 map을 이용해야 한다.

int-string형식은 array는 O(1) map은 O(logN)이므로 어떤 것을 써도 크게 시간 차이는 나지 않는다.

 

 

 

문제 구현 시 주의점

ios_base::sync_with_stdio(false); 이것으로 입출력 시간을 줄여 주지 않으면 시간 초과가 난다.

 

 

 

 

코드 구현

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


using namespace std;

map<int, string> m1;
map<string, int> m2;   //map을 통해 시간을 줄여줌
int main() {
	ios_base::sync_with_stdio(false);  ///입출력 시간 줄여줌
	cin.tie(0);
	cout.tie(0);
    
	int N, M;
	string str, q;
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		cin >> str;
		m1.insert(make_pair(i + 1, str));
		m2.insert(make_pair(str, i + 1));
	}
	for (int i = 0; i < M; i++) {
		cin >> q;
		if (atoi(q.c_str()) != 0) {   //string을 숫자로 만드는 방법 atoi(q.c_str()) 중요!
			cout << m1[atoi(q.c_str())] << "\n";  
		}
		else {
			cout << m2[q] << "\n";
		}
	}
}