[C++][Baekjoon][map] 1620 나는야 포켓몬 마스터(map/arr 시간복잡도, map value로 key찾기)

[문제]

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

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어진다.

N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다.

 

둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어온다.

 

그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어온다.

 

최종적으로 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하는 문제다.

 

[해결방법]

*1차시도:

포켓몬 도감을 map<int, string> mp; 로 표현했다.

문제가 string인지 숫자인지 판별한 후, string이면 map value로 key 를 찾도록하고 int면 key로 value를 찾도록 구현했다.

=> 시간초과로 실패.

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

int main() {
	int mapSize, quizNum;
	string input;
	map<int, string> mp;

	cin >> mapSize >> quizNum;
	for (int i = 1; i <= mapSize; i++) {
		cin >> input;
		mp.insert({ i, input });
	}

	for (int i = 0; i < quizNum; i++) {
		cin >> input;
		//문자
		if (atoi(input.c_str()) == 0) {
			for (auto& it : mp) {
				if (it.second == input) {
					cout << it.first << "\n";
				}
			}
		}
		//숫자
		else {
			cout << mp[stoi(input)] << "\n";
		}
	}
	return 0;
}

문제를 푸는 2번째 for문에서 value로 key 값을 찾을 때 map이 iterator 순회를 해야하므로 최악의 경우 n*n = 100,000*100,000 = 10,000,000,000의 시간복잡도가 발생할 수 있다. 100억ㅎ. 제한시간이 1초이므로 1억 미만이 나와야하는데 당연히 시간초과이다.

 

*2차시도: 답안처럼 map과 array 자료구조 2개 사용하기.

string 으로 int 를 찾을 때,

map 의 시간복잡도는 O(logN) / array 의 시간복잡도는 O(n)이다. (map 이 레드블랙트리 기반으로 탐색해서 O(logN) 이 걸린다.)

 

int 로 string 을 찾을 때,

map 의 시간복잡도는 O(logN) / array 의 시간복잡도는 O(1) 이다. ex) arr[1] = "Bulbasaur"

 

따라서, array 와 map 자료구조 두개를 각각의 경우에 사용하면 시간복잡도를 최종적으로 O(N)으로 줄일 수 있다.

 

[알아둘 것]

* 입력받은 값이 문자열인지 판독하는 함수: atoi(s.c_str()). 값이 0이면 문자열, 0이 아니면 숫자이다.

https://cplusplus.com/reference/string/string/c_str/

https://cplusplus.com/reference/string/string/c_str/

 

*문자열 -> 정수로 바꾸는 함수: stoi(s)

 

*map 에서 value 값으로 key 값 찾는 법: 반복문 iterator 를 이용해서 찾을 수 있다. 총 아래 3가지인데 기억나는거 쓰자!

for (auto it = map.begin(); it != map.end(); it++) {
    if (it->second == target) {
        keys.push_back(it->first);
    }
}

for (auto& it : mp) {
    if (it.second == target) {
        cout << it.first << "\n";
    }
}

for (pair<int, string> p : mp) {
    if (p.second == target) {
        cout << p.first << "\n";
    }
}

 

[코드]

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

int main() {

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

	int mapSize, quizNum;
	string input;

	cin >> mapSize >> quizNum;

	map<string, int> mp;
	vector<string> v(mapSize + 1, "");

	//도감 정보
	for (int i = 1; i <= mapSize; i++) {
		cin >> input;
		mp.insert({ input, i });
		v[i] = input;
	}

	//문제
	for (int i = 0; i < quizNum; i++) {
		cin >> input;
		//문자
		if (atoi(input.c_str()) == 0) {
			cout << mp[input] << "\n";
		}
		//숫자
		else {
			cout << v[stoi(input)] << "\n";
		}
	}
	return 0;
}

 

참고로

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

요 코드를 입력해줘야 시간초과가 해결된다. 관련 내용은 아래 포스팅 참고.

 

https://i-believe-in-me.tistory.com/387

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