[백준(BOJ)] 나는야 포켓몬 마스터 이다솜(1620번)_C++

자료구조 map을 이용하면 쉽게 해결할 수 있을 줄 알았다.

 

문제에서 입력이 숫자로 주어지거나 문자로 주어질 수 있다.

만일 map<int, string> 을 사용하다 가정하자.

입력으로 숫자가 주어지면 find() 함수를 이용해 O(log n)으로 굉장히 빠른 시간내에 번호에 해당하는 이름을 알 수 있다.

 

반대로 문자가 주어지면 for문으로 iterator를 통해 각각의 데이터에 접근해야 한다.

때문에 O(n)으로 굉장히 늦게 정답을 구해내고, 모든 입력이 문자로만 주어진다면 O(mn)으로 시간초과가 발생한다.

 

이를 해결하고자 나는 <번호, 이름>, <이름, 번호> 인 map 2개를 선언했다.

입력으로 무엇이 들어오든 O(log n) 만에 정답을 찾아낼 수 있어서 시간초과가 발생하지 않는다.

 

추가적으로 atoi() 함수를 사용할 때 인자로 string을 그대로 넘기면 컴파일 에러가 발생한다.

atoi() 함수의 인자는 const char * 형이므로 string 형을 인자로 받을 수가 없다.

때문에 문자열의 첫번째 문자의 주소를 넘겨주면 정상적으로 사용할 수 있다.

 

#include <iostream>
#include <map>

using namespace std;

int n, m;
map<int, string> dict1;
map<string, int> dict2;

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

	//input
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		string s;
		cin >> s;

		dict1.insert({i, s});
		dict2.insert({s, i});
	}
	
	//find answer
	while (m--){
		string s;
		cin >> s;

		int num;
		string name;
		if (s[0] >= '0' && s[0] <= '9'){ //input is number
			num = atoi(&s[0]);
			name = (*dict1.find(num)).second;

			//output
			cout << name << "\n";
		}
		else{ //input is character
			name = s;
			num = (*dict2.find(name)).second;
			
			//output
			cout << num << "\n";
		}
	}
}