[C++] 백준 1620 : 나는야 포켓몬 마스터 이다솜

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int N, M;
string str;
map<string, int> m; // map 찾기 O(logN) - string으로 int 찾기
vector<string> v; // int로 string 찾기
int main(int argc, char** argv){
  ios::sync_with_stdio(false);
  cin.tie(NULL); // cin, cout 시간 줄이기

  cin >> N >> M;

  for(int i=1; i<=N; i++){
    cin >> str;
    m.insert(make_pair(str, i));
    v.push_back(str);
  }

  for(int i=0; i<M; i++){
    cin >> str;
    int n = atoi(str.c_str());
    if(n){ // 숫자인지 판별 - 0이면 문자열 or 0 (도감은 1부터 시작)
      cout << v[n-1] << "\n";
    } else {
      cout << m[str] << "\n";
    }
  }

  return 0;
}

원래 pair를 사용해서 반복문을 돌면서 출력하도록 하였지만 시간 초과가 발생하였다. 탐색 시간을 줄이기 위해서는 map이 더 효율적이라는 것을 아게 되었다.

map은 pair의 업그레이드 버전이라고 생각하면 편할 것 같다. key와 value를 pair를 사용해서 풀면 된다. 다른점은 str을 key값으로 사용해 간단하게 int형인 value를 구할수가 있다. key값을 index로 사용하여 빠른 조회를 할 수 있다는 것이 강점. 이 때의 시간 복잡도는 O(logN)이라고 한다. 확실히 그냥 반복문을 돌때의 O(N)보다 빠르다.

pair는 구조체고 map은 pair와 다르게 key값이 중복될 수 없다. 또한 map은 트리구조이기 때문에 중위순위 형태로 출력이 되며 검색할 때는 binary_search와 같은 형태를 띄나보다.

따라서 search는 빠르지만 insert, delete는 느리다는 것이 특징.

시간 초과 코드

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int N, M;
string str;
vector<pair<string, int> > v;
int main(int argc, char** argv){
  scanf("%d %d", &N, &M);

  for(int i=1; i<=N; i++){
    cin >> str;
    v.push_back(make_pair(str, i));
  }

  for(int i=1; i<=M; i++){
    cin >> str;
    int n = atoi(str.c_str());
    if(n){ // 숫자인지 판별 - 0이면 문자열 or 0 (도감은 1부터 시작)
      for(int j=0; j<N; j++){
        if(v[j].second == n){
          cout << v[j].first << "\n";
        }
      }
    } else {
      for(int j=0; j<N; j++){
        if(v[j].first == str){
          cout << v[j].second << "\n";
        }
      }
    }
  }

  return 0;
}