[BOJ] 1620 - 나는야 포켓몬 마스터 이다솜

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

---

[알고리즘풀이]

포켓몬도감의 N번 째를 출력하는 경우는 시간 복잡도가 O(1)로 간단합니다.

하지만, 포켓몬도감에서 특정 Name을 가진 포켓몬이 몇 번째인지 찾는 문제는 Linear Search로는 O(n)이 되므로

시간 초과 문제에 걸립니다.

따라서, 포켓몬 도감을 Sort한 후 Binary Search를 통해 풀어줘야 합니다.

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

typedef struct poketmon{
	string name;
	int index;
};

poketmon l[100000];
string l2[100000];

bool cmp(poketmon input1, poketmon input2) {
	if (input1.name > input2.name)
		return true;
	return false;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;
		l[i].index = i;
		l[i].name = input;
		l2[i] = input;
	}
	sort(l, l + n, cmp);

	for (int i = 0; i < m; i++) {
		string input;
		cin >> input;
		if (1 <= input[0] - '0' && input[0] - '0' <= 9) {
			int temp = stoi(input);
			cout << l2[temp - 1] << '\n';
		}
		else {
			int left = 0, right = n - 1;
			while (left <= right) {
				int mid = (left + right) / 2;
				if (l[mid].name == input) {
					cout << l[mid].index + 1 << '\n';
					break;
				}
				else if (l[mid].name > input) {
					left = mid + 1;
				}
				else
					right = mid - 1;
			}
		}
	}
}

---