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

문제

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

문자열을 n개 입력하면 m개의 문자열 또는 숫자를 입력할 수 있습니다.

만약 문자를 입력하면 몇번째로 입력이 들어왔는지 출력하고

숫자를 입력하면 숫자에 해당하는 순서에 들어온 문자열을 출력하면 됩니다.

---

숫자를 입력하면 단순히 pair 형으로 string과 순서를 쌍으로 입력받아 바로 출력해주면 됩니다.

하지만 문자를 입력하면 수많이 들어온 문자열을 다 찾아가면서 찾아야 합니다.

그렇게 되면 시간이 많이 걸립니다.

 

총 2가지 방법이 있습니다.

1. 이분탐색

2. map

---

첫번째 이분탐색 방법입니다.

for (int i = 1; i <= n; i++) {
	string st;
	cin >> st;
	v.push_back({ st,i });
	p.push_back({ st,i });
}
sort(v.begin(), v.end());
sort(p.begin(), p.end(),cmp);

v벡터 와 p 벡터에 string과 int를 pair 형태로 받아줍니다.

v벡터는 string을 기준으로 오름차순 정렬하고

p벡터는 int를 기준으로 오름차순으로 정렬합니다.

while (m--) {
    string st;
    cin >> st;
    int ans = atoi(st.c_str());
    int mid;
    int l = 0;
    int r = n - 1;
    if (ans != 0) {
        while (l <= r) {
            mid = (l + r) / 2;
            if (p[mid].second < ans)
                l = mid + 1;
            else if (p[mid].second > ans)
                r = mid - 1;
            else break;
        }
        cout << p[mid].first << '\n';
    }
    else {
        while (l <= r) {
            mid = (l + r) / 2;
            if (v[mid].first < st)
                l = mid + 1;
            else if (v[mid].first > st)
                r = mid - 1;
            else break;
        }
        cout << v[mid].second << '\n';
    }
}

m개의 문자열 또는 숫자를 입력받습니다. 

일단 문자열을 입력받을지 숫자를 입력받을지 모르기때문에 일단 int형으로 바꿔줘야 합니다.

string을 char* 형으로 바꾸고 int형으로 바꿔줘야 합니다.

먼저 c_str() 함수를 통해 string을 char* 형으로 바꿔줍니다.

그 다음 char*을 int형으로 바꾸기 위해 atoi() 함수를 사용합니다.

atoi 함수는 char* 중에 숫자가 들어오면 숫자 그대로 int형으로 바꿔주지만 문자가 들어오면

바로 int형 0을 출력합니다. (stoi 함수는 string을 바로 int형으로 바꿔줍니다.)

다음 부터는 평소 하던 대로 이분탐색으로 진행하였습니다.

---

두번째 map 방법입니다.

---

전체 코드입니다.

1)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
#define inf LONG_MAX
#define big(a, b) a > b ? a : b
using namespace std;
using ll = long long;
using ull = unsigned long long;
vector<pair<string, int>>v;
vector<pair<string, int>>p;
bool cmp(pair<string, int>a, pair<string, int>b);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        string st;
        cin >> st;
        v.push_back({ st,i });
        p.push_back({ st,i });
    }
    sort(v.begin(), v.end());
    sort(p.begin(), p.end(),cmp);
 
    while (m--) {
        string st;
        cin >> st;
        int ans = atoi(st.c_str());
        int mid;
        int l = 0;
        int r = n - 1;
        if (ans != 0) {
            while (l <= r) {
                mid = (l + r) / 2;
                if (p[mid].second < ans)
                    l = mid + 1;
                else if (p[mid].second > ans)
                    r = mid - 1;
                else break;
            }
            cout << p[mid].first << '\n';
        }
        else {
            while (l <= r) {
                mid = (l + r) / 2;
                if (v[mid].first < st)
                    l = mid + 1;
                else if (v[mid].first > st)
                    r = mid - 1;
                else break;
            }
            cout << v[mid].second << '\n';
        }
    }
 
    return 0;
}
bool cmp(pair<string, int>a, pair<string, int>b) {
    return a.second < b.second;
}