[알고리즘/문제] 백준 1620번: 나는야 포켓몬 마스터 이다솜 (C++)

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

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

 

 

이 문제에서 고민을 두번 했다.

1. string형인지 int형인지 어떻게 알고 어떤 변수에 입력을 받을지를 정해놓아야하지?

2. 메인로직은 배열을 쓰면서 find 함수와 인덱스로 하려고 했는데 시간초과가 뜬다.

 

1번은 atoi를 사용해 해결을 했다.

atoi를 통해 입력받은 값이 문자열인지 숫자인지 구별할 수 있다.

 

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

string s, dogam[100001];
int n, m;


int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> dogam[i];
	}

	for (int i = 0; i < m; i++) {
		cin >> s;
		if (atoi(s.c_str()) == 0) {
			cout << find(dogam, dogam+100001, s) - dogam << '\n';
		}
		else {
			cout << dogam[atoi(s.c_str())] << '\n';
		}
	}
	return 0;
}

 

위와 같이 코드를 짰는데, 문제는 시간초과가 걸렸다.

find 함수는 시간복잡도가 O(N)이다.

그래서 이것보다 더 적은 시간복잡도를 가지는 로직을 짜야했다.

그래서 map을 이용해 구현해보았다.

map의 내부 구현은 검색, 삽입, 삭제가 O(logN)인 레드블랙트리로 구성되어 있기 때문이다.

 

그런데 문제는 map을 하나만 쓰면 value로 key를 찾아야하는데 그럴라면 또 순회를 하면서 for문을 써야한다.

그렇기 때문에 컨테이너를 두개를 사용하는 수 밖에 없는 것 같다.

 

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

map<string, int> dogam;
map<int, string> dogam2;
string s, temp;
int n, m;


int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> temp;
		dogam[temp]= i;
		dogam2[i] = temp;
	}

	for (int i = 0; i < m; i++) {
		cin >> s;
		if (atoi(s.c_str()) == 0) {
			cout << dogam[s] << '\n';
		}
		else {
			cout << dogam2[atoi(s.c_str())] << '\n';
		}
	}
	return 0;
}

 

위 코드와 같이 map을 두개를 선언해서 각각 key값을 받도록 하였다.

(숫자로 문자열을 출력하는 경우에는 배열로 해도 O(1)이라 상관은 없다.)

그래도 시간초과가 떠서 강의를 들어보니

메인함수 상단에 다음과 같은 입출력과 관련된 코드를 추가로 써줘야한다고 한다.

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

이게 무슨 의미인지는 한번 찾아봐야겠다.

 

최종적으로 다음 코드를 제출하니 정답이 되었다!

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

map<string, int> dogam;
map<int, string> dogam2;
string s, temp;
int n, m;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> temp;
		dogam[temp]= i;
		dogam2[i] = temp;
	}

	for (int i = 0; i < m; i++) {
		cin >> s;
		if (atoi(s.c_str()) == 0) {
			cout << dogam[s] << '\n';
		}
		else {
			cout << dogam2[atoi(s.c_str())] << '\n';
		}
	}
	return 0;
}

 

 

[atoi 개념정리 글]

 

[map 개념정리 글]

https://life-with-coding.tistory.com/305

[C++][STL] map 사용법 정리

 

[인프런 강의]

https://inf.run/QKBXL

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