BOJ - 1620. 나는야 포켓몬 마스터 이다솜 (C++)

1620. Map

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

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

 

[풀이]

시간복잡도에 관계없이 코드를 짜면 vector<pair<string, int>>를 사용한 구현 방법도 존재하고 map<string, int> 하나만 사용한 구현 방법도 가능하지만 모두 시간초과가 발생하며 map<string, int>와 map<int, string> 두 개의 map을 사용한 구현 방법만이 Accepted를 받을 수 있다.

 

1) 먼저 pair의 vector 를 사용한 코드를 보자

vector<pair<string, int>> a;
int N,M;
int main(){
	cin >> N >> M;
	
	for (int i=1; i<=N; i++){
		string tmp; cin >> tmp;
		a.push_back({tmp, i});
	}
	
	for (int i=0; i<M;i++){
		string tmp;	cin >> tmp;
		if (atoi(tmp.c_str()))	cout << a[atoi(tmp.c_str()) - 1].first << '\n';			
		else {
			for(int i=0; i<N; i++){
				if ( a[i].first == tmp){
					cout << a[i].second << '\n';
					break;
				}
			}	
		}
	}	
}

tmp를 M번 받을 때, tmp가 정수일 때는 a에 인덱스로 바로 접근 가능하지만,

tmp가 문자열일 때 a에 들어있는 문자열과 tmp과 같은 경우를 탐색해야 한다. 이 때 시간초과가 발생한다.

 

2) 두 번째로 map을 하나만 사용했을 때의 코드이다.

map<string, int> mp;
int N,M;
int main(){
	cin >> N >> M;	
	for (int i=1; i<=N; i++){
		string tmp;
		cin >> tmp;
		mp.insert({tmp,i});
	}
	
	for (int i=0; i<M;i++){
		string tmp;
		cin >> tmp;
		if (atoi(tmp.c_str())){
			for (auto it:mp){
				if (it.second == atoi(tmp.c_str()))	cout << it.first << '\n';			
			}
		}
		else	cout << mp[tmp] << '\n';
	}	
}

map의 key가 string 이고 value가 int 이기 때문에 tmp가 string 일 때는 tmp[string]으로 바로 접근 가능한 반면,

tmp가 정수형일 때는 바로 접근이 불가능해 하나씩 찾아야 한다. 이 때 시간 초과가 발생한다.

 

3) 세 번째 방법이 map을 두 개 쓰는 방법이다. (성공 코드)

map<string, int> mp;
map<int, string> mp2;
int N,M;
int main(){
	cin >> N >> M;	
	for (int i=1; i<=N; i++){
		string tmp; cin >> tmp;
		mp[tmp] = i;
		mp2[i] = tmp;
	}
	
	for (int i=0; i<M;i++){
		string tmp;	cin >> tmp;
		if (atoi(tmp.c_str()))	cout << mp2[atoi(tmp.c_str())] << '\n';			
		else cout << mp[tmp] << '\n';
	}	
}

map을 두 개 만들면 mp를 이용해 string으로 접근해 int를 구할 수도 있고, mp2를 이용해 int로 접근해 string을 구할 수도 있다.