Machineboy空
1620 : 나는야 포켓몬 마스터 이다솜 - map, atoi() 본문
https://www.acmicpc.net/problem/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)
- *배열이 빠르긴 하지만 크게 차이 나지 않음
- str -> int 접근하는 구조는
- ios_base::sync_with)stdio(false);cin.tie(NULL);cout.tie(NULL); 사용하지 않았더니 시간초과 발생
- map은 key를 이용해 value에 접근하는 구조.
결국 풀이 보고서 맞췄다. 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';
}
}
}
'Computer > Coding Test' 카테고리의 다른 글
1213 : 팰린드롬 - string.insert(), 홀짝 처리 (1) | 2024.02.02 |
---|---|
9375 : 패션왕 신해빈 - 경우의 수 여집합 , Map 순회 (1) | 2024.02.02 |
2559 : 수열 - 구간합, 슬라이딩 윈도우 (1) | 2024.01.31 |
9996 : 한국이 그리울 땐 서버에 접속하지 - 문자열 자르기 split, substr (1) | 2024.01.31 |
10808 알파벳 개수 / 1159 농구경기 - 카운팅 배열과 아스키코드 변환 (0) | 2024.01.30 |