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

문제

[C++] 백준 1620: 나는야 포켓몬 마스터 이다솜 SILVER 4
https://www.acmicpc.net/problem/1620

 

---

 

접근 방법

이 문제는 포켓몬 이름과 번호를 양방향으로 조회해야 하는 문제다.

 

즉,

• 이름이 주어지면 → 번호 출력
• 번호가 주어지면 → 이름 출력

이 두 가지를 모두 빠르게 처리해야 한다.

그래서 자료구조를 두 개로 나누어 사용했다.

1. map<string, int>
   → 이름 → 번호를 저장
2. vector<string>
   → 번호 → 이름을 저장

입력받을 때 포켓몬을 1번부터 차례대로 저장하면서 아래와 같이 두 자료구조에 동시에 기록한다.

dic[str] = i;      // 이름 → 번호
dic2.push_back(str); // 번호 → 이름

 

질의를 처리할 때는 입력이 문자열로 들어오므로,

• 첫 글자가 숫자라면 → stoi로 정수 변환 후 vector에서 찾기
• 알파벳이라면 → map에서 번호 찾기

이 방식으로 O(log N) 시간에 질의를 처리할 수 있다.

 

구현 시 주의할 점

• 벡터는 0번 인덱스부터 시작하지만 포켓몬 번호는 1번부터 시작하므로 번호로 접근할 때 반드시 -1을 해줘야 한다.
• 입력이 숫자인지 문자열인지 구분할 때 str[0]이 '0' ~ '9' 범위인지 확인하면 된다.
• 질의 개수가 많을 수 있으므로 빠른 입출력 설정을 해주는 것이 안전하다.
• map에서 dic[str]처럼 접근하면 존재하지 않는 키가 들어올 경우 기본값이 생성되지만,
  문제 조건상 항상 존재하는 값만 들어오므로 별도 처리는 필요 없다.

 

 

---

 

코드

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

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

	int n = 0, m = 0;
	cin >> n >> m;

	map<string, int> dic;
	vector<string> dic2;
	for (int i = 1; i <= n; i++)
	{
		string str = "";
		cin >> str;

		dic[str] = i;
		dic2.push_back(str);
	}
	for (int i = 0; i < m; i++)
	{
		string str = "";
		cin >> str;

		if ('0' <= str[0] && str[0] <= '9')
			cout << dic2[stoi(str) - 1] << '\n';
		else
			cout << dic[str] << '\n';
	}
}