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

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

 

문제 분류 : map(unordered_map)

 

전에 brute force로 풀려고 하다가 시간초과로 못 풀었던 문제다. map을 배우고 나니 풀 수 있을 것 같아서 시도해봤다.

 

N개의 포켓몬 이름(string)을 입력받고, M개의 int 혹은 string을 입력받는다. int라면 int를 index로 삼아 포켓몬의 이름을 출력하고, string이라면 해당 포켓몬의 index를 출력하면 된다.

 

1. '이름 -> 인덱스'나 '인덱스 -> 이름' 중 하나만 해도 되는 것이라면 map 하나만 써서 손쉽게 해결할 수 있지만, 둘 다를 요구하기 때문에 string을 저장해놓는 별도의 array를 만들어야 한다는 점이 까다로웠다.

 

2. cin, cout보다 printf, scanf가 유연성 측면에서 유리한 면이 있는 것 같아 연습하고 있는데 문자열을 입력받을 때 꽤나 애먹었다. scanf는 C++ library인 string을 입력받지 못하기 때문에 문자 배열을 입력받아야 한다.

 

3. map을 사용해서 통과됐는데 다른 사람들의 풀이를 보니 unordered_map을 쓴 경우가 더 많아서 unordered_map으로 수정해 제출했더니 시간이 단축되었다.

 

처음에 map을 쓴 이유는 정렬이 되어있으므로 적어도 logN 시간 안에 탐색이 가능하기 때문이다. 그에 반해 unorder_map은 평균과 최악의 경우의 시간 복잡도가 너무 극명해서 사용하기 꺼려졌다. 

 

map의 경우에는 rebalancing에 대한 비용이 계속 들어 삽입이 늦어지기 때문에 오래 걸리고, unordered_map의 경우에는 hash table을 통해 참조하기 때문에 정렬을 할 필요가 없고, 그렇기 때문에 데이터의 수가 많아지더라도 성능을 보장할 수 있다고 한다.

 

GeekforGeeks

 

#include <cstdio>
#include <unordered_map>
#include <string>
using namespace std;
char arr[100001][21];
unordered_map<string, int> m;
int main() {
  int N, M, idx;
  char ins[21];
  scanf("%d %d", &N, &M);
  for (int i = 1; i <= N; i++) {
    scanf("%s", arr[i]);
    m[arr[i]] = i;
  }
  while (M--) {
    scanf("%s", ins);
    if (ins[0] >= 'A' && ins[0] <= 'Z') {
      printf("%d\n", (*m.find(ins)).second);
    } else {
      idx = atoi(ins);
      printf("%s\n", arr[idx]);
    }
  }
}