[ 백준/C++ ] 나는야 포켓몬 마스터 이다솜

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

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

흠 백준에서 1620 바로 검색해서 찾으면 문제가 안보인다.

 

 

문자나 숫자로 들어오고 그걸 찾아야 한다.

이 부분을 보고 바로 map container를 생각해 낼 수 있다. 

 

[답안]

#include <bits/stdc++.h>

using namespace std;

/* 첫 줄 : 도감에 수록된 포켓몬 개수 N, 내가 맞춰야 하는 문제 개수 M
1보다 크거나 같고 100,000보다 작다*/

map<string, string> si;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N, M;
	cin >> N >> M;
	for (int i = 1; i < N + 1; i++) {
		string name;
		cin >> name;
		string num = to_string(i);
		si.insert({ name, num });
		si.insert({ num, name });
	}

	for (int i = 0; i < M; i++) {
		string input;
		cin >> input;
		cout << si[input] << "\n";
	}

	return 0;
}

 

[회고] map, endl? '\n'?

map : 고유한 키를 기반으로 키 - 값 쌍으로 이루어진 정렬된 연관 컨테이너 

삽입, 삭제, 수정, 탐색에 O(logN)의 시간복잡도를 가진다. 

 

고유한 키를 갖기 때문에 중복된 값이 들어갈 수 없고 오름차순 정렬된다.

 

map<string, int> mp;

mp.insert({a[i], i+1});
mp[a[i]] = i+1;

insert({key, value}) : map에다 key, value 집어 넣기 

[key] = value : 대괄호 []를 통해 key에 해당하는 value 할당

[key] : 대괄호[]를 통해 key를 기반으로 map에 있는 요소 참조

size() : map에 있는 요소들의 개수 반환

erase(key); : 해당 키에 해당하는 요소 삭제

find(key): map에서 해당 key를 가진 요소를 찾아 해당 이터레이터 반환, 만약 못찾을 경우 mp.end() 해당 map의 end() 이터레이터를 반환

for(auto it : mp) : 범위 기반 for 루프로 map 요소 순회. map을 순회할 때는 key는 first, value는 second로 참조

for(auto it = mp.begin(); it!=mp.end(); it++) : map에 있는 요소들을 이터레이터로 순회

mp.clear() : map에 있는 요소들을 모두 제거 

 

주의할 점

map의 경우 인덱스만 참조해도 맵의 요소가 생성된다. 만약 map에 해당하는 키에 요소가 없다면 0 또는 빈 문자열이 할당

아래 코드처럼 해결

#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
map<string, string> mp2;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
if(mp[1] == 0){
mp[1] = 2;
}
for(auto i : mp) cout << i.first << " " << i.second;
return 0;
}
/*
1 2

#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
map<string, string> mp2;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
if(mp.find(1) == mp.end()){
mp[1] = 2;
}
for(auto i : mp) cout << i.first << " " << i.second;
return 0;
}
/*
1 2
*/

 

endl 보단 '\n'

처음에 endl을 썼다가 시간 초과가 나왔었는데 '\n'을 쓰면 해결됐다.

endl은 '\n' + 버퍼 플러시에게 때문에 출력 싱크를 보다 '정확하게' 만들어 준다. 

버퍼 플러시는 임시 저장 영역에서 컴퓨터의 영구 메모리로 컴퓨터 데이터를 전송하는 것인데,  알고리즘에선 '\n'을 사용하는 것이 좋다!