백준 1620, 두 개의 자료구조를 사용(+ 문자열을 숫자로 바꾸기)

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

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

해당 문제는 문자열을 입력받으면 숫자를 출력하고, 숫자를 입력받으면 문자를 출력하는 문제이다.

따라서 문자(String)와 숫자(Integer)가 매핑된 자료구조를 사용해야 한다. 만약, String을 Key로 갖고 Integer가 Value인

Map을 활용하면, 문자를 입력받았을 때 숫자를 출력할 수 있다. 하지만 Integer를 입력받았을 경우, 이 자료구조로 문자열을 출력하려면 O(N)이 걸리게 된다. 따라서 Integer와 String이 매핑된 또 하나의 자료구조를 사용해야 한다.

Key Point

1. 숫자와 문자열을 매핑한 각각의 자료구조 2개를 선정한다. -> Map & Map 또는 Map & Array를 사용한다.
   • 숫자를 인덱스로 한 배열의 경우, 탐색에 O(1)이 걸리고 Map이라면 O(logN)이 걸린다. 따라서 둘 중 아무거나 사용해도 된다.
2. 입력받은 값이 숫자인지 문자인지를 판별해야 하므로 atoi()를 사용한다. -> 기본적으로 문자열을 입력받고 반환 값에 따라 자료구조를 사용해서 값을 반환한다.

문제 코드

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

map<string, int> mp;
string arr[100001];
int N, M;
string s;

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;
		arr[i+1] = s;
	}
	
	// M번 동안 입력받은 값이 숫자 혹은 문자일 때 적절한 값 반환
	for(int i = 0; i < M; i++){
		cin >> s;
		if(atoi(s.c_str()) == 0){
			// 입력이 문자임 -> 숫자 반환(map 자료구조 사용) 
			cout << mp[s] << "\n"; 
		} else {
			cout << arr[atoi(s.c_str())] << "\n";
		}
	} 

	return 0;
}

• map<string, int> mp의 경우, 문자열 Key를 통해 숫자를 출력하기 위해 사용되는 자료구조이다. 이 때 시간복잡도는 O(logN)이다.
• string arr[100001]의 경우, 숫자 인덱스를 통해 문자열을 출력하기 위해 사용되는 자료구조이다. 이 때 시간복잡도는 O(1)이다.
• atoi()의 반환 값이 0이면, 입력이 문자열이라는 뜻이고 이 때는 map에 저장된 값을 사용한다.
• atoi()의 반환 값이 정수라면, 해당 정수 인덱스에 해당하는 배열의 값을 출력하면 된다.
• 시간초과가 발생할 수 있으므로, 입출력 싱크를 해제하여 버퍼 동기화를 푼다. 그러면 cin과 cout의 속도가 빨라지게 된다.

 

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의