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

March 23, 2021 ( last updated : March 23, 2021 )
자료구조 맵과 해시 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

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

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

백준 1620번

알고리즘 유형

문제 이해

포켓몬 이름들을 저장해 두었다가 문제에 따라서 포켓몬 이름 혹은 인덱스 번호로 포켓몬을 찾는 문제

풀이 방법

unorderd_map에 넣고 풀면된다. 그냥 map과는 달리 unorderd_map은 찾는데 O(1)의 시간이 걸리기 때문에 쉽게 풀 것으로 예상되었다. 근데 시간초과가 나와서 당황했는데 원인은 i/o 성능 때문이었다. 성능 개선을 하도록 코드를 추가하니 시간이 널널하게 풀렸다.

#include <iostream>
#include <unordered_map>
#define endl '\n'
using namespace std;
int N, M;

int is_num(string str);

int main() {
  std::cin.tie(0);
  std::cin.sync_with_stdio(false);
  std::cout.tie(0);
  std::cout.sync_with_stdio(false);
  unordered_map<int, string> int_to_search;
  unordered_map<string, int> string_to_search;

  cin >> N >> M;

  for (int i = 1; i <= N; i++) {
    string pokemon;
    cin >> pokemon;
    string_to_search[pokemon] = i;
    int_to_search[i] = pokemon;
  }

  for (int i = 0; i < M; i++) {
    string question;
    cin >> question;
    if (is_num(question)) {
      cout << (int_to_search[stoi(question)]) << endl;
    } else {
      cout << (string_to_search[question]) << endl;
    }
  }
}

int is_num(string str) {
  for (auto c : str) {
    if (isdigit(c) == 0) {
      return 0;
    }
  }
  return 1;
}

Originally published March 23, 2021
Latest update March 23, 2021

Related posts :

{# #}