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

Binary_Search 문제입니다.

숫자를 입력하면 그에 해당하는 포켓몬을 출력하고
포켓몬을 출력하면 인덱스 번호를 출력해야합니다.

for문을 전부 돌며 찾게되면 O(N)번의 작업이 필요합니다.
하지만 N은 10만이므로 반복해서 수행하면 시간초과가 날 수 있습니다.

문자열로 정렬을해서 이분탐색을 통해서 탐색해줍니다.
이는 O(N)에서 O(longN)으로 줄여줍니다.

그리고 숫자를 입력받는 경우에는 그대로 입력받은 배열을 한개 둬서
인덱스 자체로 접근하여 O(1)로 접근할 수 있습니다.

 

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

int n, m;
int result;
int low, high;
int mid;
string s;
vector<string> v1;
vector<pair<string, int> > v2;

int main(int argc, char* argv[])
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	v1.push_back("");
	for (int i = 1; i <= n; ++i) {
		cin >> s;

		v1.push_back(s);
		v2.push_back({ s, i });
	}

	sort(v2.begin(), v2.end());	

	for (int i = 1; i <= m; ++i) {
		cin >> s;

		if (s[0] >= '0' && s[0] <= '9') {
			result = stoi(s);
			cout << v1[result] << "\n";
		}
		else {
			low = 0;
			high = n - 1;

			while (low <= high) {
				mid = (low + high) / 2;
			
				if (v2[mid].first == s) {
					cout << v2[mid].second << "\n";
					break;
				}
				else if (v2[mid].first < s) {
					low = mid + 1;
				}
				else {
					high = mid - 1;
				}
			}
		}
	}

	return 0;
}