1620 : 나는야 포켓몬 마스터 이다솜 - map, atoi()

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

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

 

문제요약

숫자와 포켓몬 이름이 매핑되어 있는 도감에,

숫자를 넣으면 포켓몬 이름이, 포켓몬 이름을 넣으면 숫자를 출력.

 

난이도

Silver 4

---

풀이

• 입력값이 숫자인지 문자인지 판단
  • atoi(), stoi()
  • *atoi()사용하지 않는 방법 추후 추가
• 배열과 map의 탐색 시간복잡도
  • 배열 탐색 : O(N)
  • map 탐색 : O(logN)
• ios_base::sync_with)stdio(false);cin.tie(NULL);cout.tie(NULL);
  • iostream 라이브러리와 stdio라이브러리 동기화 끊기
  • cin-cout간의 tie 해제
  • 대량의 입력을 처리할 때 사용.

---

REVIEW

 

• 1차 시도
  • 배열로 풀었더니 시간초과가 나서 map으로 바꿔야 겠다고 생각.
  • stoi()나 atoi()를 생각해내지 못해서 아스키코드를 활용해 문자인지 숫자인지 분간하는 조건부 작성.
• 2~ n차 시도 
  • map은 key를 이용해 value에 접근하는 구조.
    • str -> int 접근하는 구조는
      • map<string, int>를 사용해 탐색하는 것이 가장 빠름 O(logN)
    • int -> str 접근하는 구조는
      • map<int, string> 탐색 시, O(logN)
      • string a[n] 배열 탐색 시, O(1)
      • *배열이 빠르긴 하지만 크게 차이 나지 않음
  • ios_base::sync_with)stdio(false);cin.tie(NULL);cout.tie(NULL); 사용하지 않았더니 시간초과 발생

결국 풀이 보고서 맞췄다. map과 배열의 탐색 시간 복잡도를 바로 떠올려서 적절한 자료구조를 사용할 수 있도록!

---

문법정리

• int atoi(string);
  • ASCII to Integer
  • 문자열이 문자라면 0을 반환, 숫자라면 숫자를 반환
  • 반환값이 0일 때 숫자 0인지 문자인지는 구분할 수 없음.
• int stoi(string);
  • String to Integer
  • 10진법 기반 변환임.

---

CODE

#include <bits/stdc++.h>
using namespace std;

int N,M;
string s;

map <string, int> mp;
string a[100004];

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); 

    cin >> N >> M;

    for(int i = 0; i < N; i++){
        cin >> s;
        mp[s] = i+1;
        a[i+1] = s;
    }

    for(int i = 0; i < M; i++){
        cin >> s;
        
        if(atoi(s.c_str())==0){
            cout << mp[s] <<'\n';

        }else{

            cout << a[atoi(s.c_str())]<<'\n';
        }
    }


}