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

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

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

소스 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

typedef struct 
{
	int number;
	string name;
}Pokemon;

bool compare(Pokemon a, Pokemon b)
{
	return a.name < b.name;
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int N, M;
	cin >> N >> M;
	vector<Pokemon> p;
	vector<Pokemon> p_n;
	vector<string> dir;
	Pokemon pok;
	
	for (int i = 0;i < N;i++)
	{
		pok.number = i + 1;
		cin >> pok.name;
		p.push_back(pok);
		p_n.push_back(pok);
		dir.push_back(pok.name);
	}

	sort(p.begin(), p.end(),compare);

	for (int i = 0;i < M;i++)
	{
		string element;
		cin >> element;
		if (element[0] >= 48 && element[0] <= 57)
		{
			int element_n = stoi(element)-1;
			cout << p_n[element_n].name << '\n';
		}

		else
		{
			int start = 0;
			int end = dir.size() - 1;
			int mid;
			while (start <= end)
			{
				mid = (start + end) / 2;
				if (p[mid].name == element)
				{
					cout << p[mid].number << '\n';
					break;
				}

				else if (p[mid].name < element)
					start = mid + 1;

				else if (p[mid].name > element)
					end = mid - 1;
			}
		}
	}
}

 

마무리 : 처음에 이 문제를 벡터 2개를 만들어 브루트포스 알고리즘을 이용하여 비교하는 코드를 짰다. 그렇게 하니 시간이 초과하여 sort와 이진 탐색을 이용하여 시간을 줄이게 만들었다. 그리고 입력된 이름이 첫글자가 대문자이므로 아스키코드를 숫자로 바꾸어 그에 해당하는 순번을 출력한다. 다른 사람이 풀었던 문제를 보면 맵을 이용하여 풀었는데 나처럼 구조체로 구하지 않는 것이 좋다.(괜히 코드만 복잡할 뿐이다)