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

https://www.acmicpc.net/problem/1620

단계별로 풀어보기

14단계(집합과 맵) 4번째

 

 

 

map은 레드-블랙 트리를 기반으로 구현되어 있어 key를 이용해 value를 찾기는 쉽지만 value를 이용해 key를 찾을 수는 없으며 O(n) 전체 순회가 유일한 방법이다.

PS에서 map을 쓰면서 양방향 탐색이 필요하다면 메모리를 두 배 써서 map을 2개 만드는 방식이 가장 정석이라고 할 수 있다.

 

 

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  map<int, string> mp;
  map<string, int> mp2;
  
  cin >> n >> m;
  
  for(int i=1;i<=n;i++){
    string p;
    
    cin >> p;
    
    mp[i]= p;
    mp2[p]= i;
  }
  
  while(m--){
    string q;
    
    cin >> q;
    
    if(q[0]<'A'){ // 숫자or문자 체크를 아스키코드 값 비교로 대체
      cout << mp[stoi(q)] << "\n";
    }else{
      cout << mp2[q] << "\n";
    }
  }
  
  return 0;
}