백준 1620 - 나는야 포켓몬 마스터 이다솜

C++

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

문제

문제가 많이 길다..
요약하면 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어오며, 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어온다.
문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해하여라.
문제 출처

접근 방법

문제로 숫자를 입력받으면 인덱스로 접근하여 해당하는 포켓몬을 뽑아 낼 수 있다.
하지만 포켓몬 이름으로 입력을 받고 해당하는 번호를 전체 탐색을 하여 찾는 방법은 O(n)으로 해당하는 문제에서는 시간초과가 나온다.
따라서 대량의 데이터 탐색에 효과적인 Hash Map(여기선 unordered_map)으로 사용하여 해결하였다.

구현

숫자로 접근하는 경우 포켓몬 String 값이 들어잇는 vector<string>,
문자열로 접근하는 경우 <포켓몬 이름, 번호>로 이루어진 unordered_map<string, int>으로 접근하여 번호를 찾아낸다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>

using namespace std;

int n, m;
vector<string> pokemon;
vector<string> inputStr;
unordered_map<string, int> pokemonMap;

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

	cin >> n >> m;
	string curPK;
	//N개의 포켓몬
	for (int i = 0; i < n; i++) {
		cin >> curPK;
		pokemon.push_back(curPK);
		pokemonMap.insert(make_pair(curPK, i + 1));
	}
	//M개의 문제
	for (int i = 0; i < m; i++) {
		cin >> curPK;
		inputStr.push_back(curPK);
	}

	//출력
	for (int i = 0; i < inputStr.size(); i++) {
		string curStr = inputStr.at(i);
		//string의 첫 char만 확인하여 아스키코드로 숫자인지 string인지 판별한다.
		if ('0' <= curStr[0] && curStr[0] <= '9') {
			//숫자 -> 인덱스로 참조하여 value값 (포켓몬)을 찾는다
			cout << pokemon[stoi(curStr) - 1] << "\n";
		}
		else {
			//문자열 -> 해시맵으로 빠르게 value값 (포켓몬 번호)를 찾는다.
			cout << pokemonMap[curStr] << "\n";
		}
	}

	return 0;
}

후기 및 개선할 점

포켓몬 이름을 탐색하는 방법으로 이분 탐색으로도 연습 할 수 있도록 한다.