문제

문제 링크

어떻게 접근할 것인가

  • index로 찾는다고 하면 그냥 어레이의 index값을 출력하면 된다.
  • 하지만 이름으로 찾는다고 binary search를 위해 정렬된 어레이가 필요하다.
  • 이를 위해서 어레이를 하나 더 준비하고 여기에는 이름과 index를 같이 넣어준 후 찾고자 하는 이름의 이전 위치를 찾기 위해 upper_bound를 진행하였다.
  • 그 후 찾아진 값에 저장되어있는 인덱스 값을 출력합니다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define psi pair<string, int>
using namespace std;

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n, m;
    string temp;
    cin >> n >> m;
    vector<psi> s(n); 
    vector<string> v(n);
    for(int i = 0; i < n; i++){
        cin >> temp;
        s[i] = psi(temp, i);
        v[i] = temp;
    }
    sort(s.begin(), s.end());
    for(int i = 0; i < m; i++){
        cin >> temp;
        if(temp[0] > '9') cout << s[upper_bound(s.begin(), s.end(), psi(temp, -1)) - s.begin()].second + 1<< '\n';
        else cout << v[stoi(temp) - 1] << '\n'; 
    }
}

느낀점

  • pair에서 인덱스 값을 찾는 방법으로다가 업퍼바운드를 사용한거는 좀 신박했다 ㅎㅎㅎ
  • 역시 고생을 한 경험에서 나오는 바이브인가보다.