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

문제 링크입니다: https://www.acmicpc.net/problem/1620

재밌는 이분 탐색 문제였습니다.

알고리즘은 아래와 같습니다.

1. 인덱스가 입력될지 이름이 입력될지 모르기 때문에 M개의 입력을 모두 string으로 입력 받습니다. 만약 숫자라면 integer형으로 변환합니다.

2. 이름이 입력된다면 이분 탐색을 진행해야하므로 별도의 벡터(sortV)를 선언하여 이름순으로 정렬합니다.(이분 탐색을 위해 pair<string, int> 형으로 선언하고 second에 기존의 인덱스를 저장합니다.)

3. 인덱스가 입력되면 O(1)로 바로 접근하고 이름이 입력되면 O(logN)으로 이분탐색을 진행하면 됩니다!

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, M;

        cin >> N >> M;

 

        vector<string> v(N + 1);

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

                 cin >> v[i];

 

        //이분 탐색을 위해 선언한 벡터

        vector<pair<string, int>> sortV(N);

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

        {

                 sortV[i].first = v[i + 1];

                 sortV[i].second = i + 1;

        }

       

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

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

        {

                 string s;

                 cin >> s;

 

                 //인덱스가 입력될 경우

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

                 {

                         int idx = 0;

                         for (int j = 0; j < s.length(); j++)

                         {

                                 idx += s[j] - '0';

                                 idx *= 10;

                         }

                         idx /= 10;

                         cout << v[idx] << "\n";

                 }

                 //이름이 입력될 경우 이분 탐색하는 경우

                 else

                 {

                         int low = 0, high = N - 1;

                         while (low <= high)

                         {

                                 int mid = (low + high) / 2;

                                 //cout << low << " " << mid << " " << high << "\n";

                                 if (sortV[mid].first == s)

                                 {

                                          cout << sortV[mid].second << "\n";

                                          break;

                                 }

                                 else if (sortV[mid].first < s)

                                          low = mid + 1;

                                 else

                                          high = mid - 1;

                         }

                 }

        }

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~