백준(BOJ) 1620번 나는야 포켓몬 마스터 이다솜

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

문제

오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.

나의 풀이:

N과 M이 10만 이기때문에 완전탐색으로는 10만 * 10만이 되어서 시간 내에 불가능하다. 이분탐색으로 접근하여야 가능하다. 그런데 숫자가 주어젔을 경우

에는 이분탐색으로 접근하지 않고 바로 인덱스로 접근해도 해결이 가능하다. 

따라서 숫자시 인덱스로 바로 접근 , 알파벳일시 이분 탐색으로 접근해주자.

 숫자로 접근하고 알파벳 접근후 다시 숫자로 접근하여야 하는 상황도 있으므로 알파벳 접근시 알파벳 정렬을 하기 때문에 다시 인덱스

로 접근할 수 없게 된다. 따라서 복사 배열을 하나 만들어서 알파벳 용으로 취하고 원래 배열은 숫자 용으로 취하자.

코드 ( C ++ )

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int N, M;

vector<pair<int, string>> book;

bool compare(pair<int, string> a, pair<int, string> b)

{

return a.second < b.second;

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(0);

cin >> N >> M;

// 배열이 1부터 접근하도록 쓰지않는 값을 book[0]에 저장해두었다.

book.push_back(make_pair(0, "dummy"));

for (int i = 1; i <= N; ++i)

{

string s;

cin >> s;

book.push_back(make_pair(i, s));

}

// 알파벳이 들어왔을 경우를 위한 복사 벡터 선언

vector<pair<int, string>> copyBook(N + 1);

for (int i = 1; i <= N; ++i)

{

copyBook[i].first = book[i].first;

copyBook[i].second = book[i].second;

}

// 알파벳용 복사배열을 알파벳순으로 정렬한다. ( 이분탐색을 위함 )

sort(copyBook.begin() + 1, copyBook.end(),compare);

for (int i = 1; i <= M; ++i)

{

string s;

cin >> s;

// 숫자가 들어오는 경우 숫자로 바꿔서 바로 인덱스로 접근

if ('0' <= s[0]&& s[0] <= '9') {

int num = stoi(s);

cout << book[num].second << "\n";

}

// 이름이 들어오는 경우 이분탐색으로 접근

else {

int small = 1;

int big = N;

while (small <= big) {

int mid = (small + big) / 2;

if (copyBook[mid].second == s) {

cout << copyBook[mid].first << "\n";

break;

}

else if (copyBook[mid].second > s)

big = mid - 1;

else

small = mid + 1;

}

}

}

return 0;

}