C++) 백준 1620번: 나는야 포켓몬 마스터 이다솜

이틀동안 이것저것 알아본다고 PS에 손을 대지 않았다.

이틀 안했다고 그새 뻑뻑해진 느낌.. 하루도 거르지 않는 습관을 들이자.

 

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

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

map 사용 문제이다. 풀고난 후의 관전 포인트는 '처음에 map을 선언할 때 key와 value의 자료형을 어떻게 지정할 것인가'인 듯 하다.

 

< 풀이 방법 1 - 시간 초과 >

처음 풀 때도 정답은 나오기는 했다. 그러나 이 문제는 시간 초과를 어떻게 피하느냐가 주된 목표인 듯.

처음에는 map을 선언할 때 map<int, string>으로 선언했다. 도감이니까 int를 key로 찾는 게 편할 것 같아서..?

그런데 이렇게 하니 문제의 목표 중 한 가지인 string으로 int를 찾는 게 여의치 않았다. 반복문을 한 번 더 돌려서 iterator로 하나씩 검사하여 찾아야 했던 것. 아마도 여기서 시간 초과가 발생한 것 같다.

 

< 풀이 방법 2 - 성공 >

int는 배열의 인덱스로 찾아야겠다 싶어서 string 배열을 하나 더 만들고 map의 형태를 map<string, int>로 바꿔주었다. 따라서 찾아야 하는 값이 문자면 map을 사용하고 숫자면 string 배열에서 인덱스 형태로 뽑아서 썼다.

 

아래는 코드이다.

 

#include <iostream>
#include <algorithm>
#include <map>
#include <string>  // stoi() 함수 이용

using namespace std;

map<string, int> book;
string book_str[100001];

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

int N, M;
cin >> N >> M;

string poketmon;
for (int i = 1; i <= N; i++) {
cin >> poketmon;
book.insert({ poketmon, i });
book_str[i] = poketmon;
}

string problem;
for (int i = 0; i < M; i++) {
cin >> problem;
if (book.find(problem) != book.end()) {
cout << book.find(problem)->second;
}
else {
int problem_int = stoi(problem);
cout << book_str[problem_int];
}
cout << "\n";
}

return 0;
}