[C++] 백준 1620번 나는야 포켓몬 마스터 이다솜

1. 문제이해

1620번: 나는야 포켓몬 마스터 이다솜 (acmicpc.net)

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

 

첫째 줄에 도감에 수록된 포켓몬의 수 N과 맞춰야할 문제의 개수 M이 주어진다.

둘째줄부터, 번호가 1부터 N까지에 해당하는 포켓몬들을 차례로 입력한 후,

입력이 끝나면 M개의 문제를 입력한다.

이때, 번호가 입력되면 해당 번호에 해당하는 포켓몬의 이름을,

이름이 입력되면 해당 이름을 가진 포켓몬의 번호를 출력해야한다.

위와 같은 프로그램을 구현하는 것이 이번 문제의 목표이다.

 

 

 

2. 문제풀이

 

1번부터 N번까지의 포켓몬의 이름을 입력받고, M개의 문제를 풀이해 출력하면 되는 문제이다.

주의해야 할 점은, 문제에서 번호가 입력되면 해당 번호에 해당하는 포켓몬의 이름을,

이름이 입력되면 해당 이름을 가진 포켓몬의 번호를 출력해야한다는 것이다.

 

문제 자체는 어렵지 않다.

다만, 해당 문제에서 주의해야 할 점이 하나 있는데, 바로 시간초과이다.

class나 배열을 이용하게 되면, 문제를 푸는 과정에서 여러번 for문을 사용하게 된다.

(번호가 입력되면 이름을 찾고, 이름이 입력되면 번호를 찾는 과정에서,

해당 배열, 클래스 내에 동일한 값이 있는지를 찾는데 for문을 이용하게 된다.)

해당 문제에서는 위와 같이 풀이 시, 가차없이 시간초과가 발생했다.

(N, M의 범위가 100,000까지여서 연산 시, 시간이 상당히 많이 발생한다.)

 

따라서 필자는 map container를 사용해 코드를 구현했다.

map 은 key와 value가 쌍으로 지정되는 컨테이너로, 균형 이진트리 구조를 띄고 있다.

key값과 value값을 쌍으로 저장할 수 있다는 점을 이용해,

포켓몬의 이름과 포켓몬의 번호를 함께 짝지어 저장해주도록 했다.

또한, 해당 컨테이너에서 find() 를 통해 for문 연산 없이 빠르게 값을 찾을 수 있도록 했다.

아래 소스코드에는 class를 이용한 코드와 map을 이용한 코드 모두 적어놓았다.

 

map에 대한 자세한 설명은 아래 블로그에 잘 설명되어있으니 참고 바랍니다.
https://life-with-coding.tistory.com/305#comment17087072

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

 

 

 

 

3. 소스코드

1. class를 이용한 코드 (시간초과)

#include <iostream>
#include <cctype>
#include <string>
#include <algorithm>
using namespace std;

// 입력받은 포켓몬을 저장할 클래스
class pokemon {
public:
	string pokemon_name;
	int pokemon_num;
};

pokemon* P = new pokemon[100000];

int main() {
	int N;               // 도감에 수록된 포켓몬 수
	int M;               // 맞춰야 하는 문제의 수
	string input_name;   // 맞춰야 되는 문제 중 입력된 이름
	int input_num;       // 맞춰야 되는 문제 중 입력된 번호

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> P[i].pokemon_name;
		P[i].pokemon_num = i;
	}

	for (int i = 0; i < M; i++) {
		cin >> input_name;
        
		// 1. 입력된 것이 숫자인 경우
		if (isdigit(input_name[0]) != 0) {
			input_num = stoi(input_name) - 1;
			for (int j = 0; j < N; j++) {
				if (input_num == P[j].pokemon_num) {
					cout << P[j].pokemon_name << "\n";
				}
			}
		}
        
		// 2. 입력된 것이 문자인 경우
		else {
			for (int j = 0; j < N; j++) {
				if (input_name == P[j].pokemon_name) {
					cout << P[j].pokemon_num + 1 << "\n";
				}
			}
		}
	}

	return 0;
}

class를 이용해 풀이한 코드로, 백준에서는 시간초과가 발생했다.

문제를 푸는 과정의 코드 부분에서, 입력된 값과 동일한 값을 찾는데 for문을 이용하게 되어

상당히 많은 시간이 소요, 따라서 시간초과가 발생한 것으로 보인다.

 

 

2. map을 이용한 코드 (성공)

#include <iostream>
#include <cctype>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

string pokemon[100000];

int main() {
	map<string, int> P;  
	int N;               // 도감에 수록된 포켓몬 수
	int M;               // 맞춰야 하는 문제의 수
	string input_name;   // 맞춰야 되는 문제 중 입력된 이름
	int input_num;       // 맞춰야 되는 문제 중 입력된 번호

	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> pokemon[i];
		P.insert(make_pair(pokemon[i], i));
	}

	for (int i = 0; i < M; i++) {
		cin >> input_name;

		// 1. 입력된 것이 숫자인 경우
		if (isdigit(input_name[0]) != 0) {
			input_num = stoi(input_name) - 1;
			cout << pokemon[input_num] << "\n";
		}

		// 2. 입력된 것이 문자인 경우
		else {
			auto index = P.find(input_name);
			cout << index->second + 1 << "\n";
		}
	}

	return 0;
}

map을 이용한 코드로, 먼저 도감에 저장된 포켓몬의 수(N)와 문제 수(M)를 입력받는다.

N만큼 포켓몬의 이름을 입력받고, 해당 포켓몬의 이름을

pokemon[i], map <string, int> P에 저장한다.

이때, pokemon[i]는 아래 1. 입력된 것이 숫자인 경우에 사용하고,

map P는 2. 입력된 것이 문자인 경우에 사용하기 위해 선언, 초기화해주었다.

 

이후, 다음 for문을 통해 M만큼 문제를 입력받고 출력한다.

input_name이라는 string 변수에 문제를 입력받고,

isdigit을 통해 입력받은 것이 숫자인 경우와 아닌 경우로 나누어 구현했다.

(isdigit값이 0이 아니면 숫자, 0이면 문자이다.)

 

 

1. 입력된 것이 숫자인 경우

해당 번호에 해당하는 포켓몬의 이름을 출력해야하므로,

입력된 input name을 int형으로 형변환 한 후, input num 에 저장해주었다.

이때, 배열에 저장된 값들은 0부터 시작하기 때문에 -1을 해주었다.

이후, pokemon[input_num] 을 통해 해당 번호의 포켓몬의 이름을 출력했다.

 

2. 입력된 것이 문자인 경우

해당 이름에 해당하는 포켓몬의 번호을 출력해야하므로,

입력된 input name을 find 함수를 이용해 찾아주고, 해당 인덱스값에서 +1을 해주었다.

여기서 +1을 해준 이유 또한, 저장된 값들은 0부터 시작하기 때문이다.

 

 

마지막으로 한가지 더 주의할 점이 있다.

바로, 입출력 속도를 향상시키기 위한 다음 두 구문이다.

cin.tie(0);
ios::sync_with_stdio(0);

위 구문을 추가하지 않을 경우 또한 시간초과가 발생했다.

cin, cout을 사용하고 싶은 경우라면 위 구문을 반드시 추가해야 할 듯 하다.

 

 

---

여러가지로 많이 헤맸던 문제였다..

분명 맞는데 왜 계속 시간초과가 날까, 왜 틀렸다고 할까.

여러번 시행착오를 겪었던것 같다. 😱

질문이나 지적은 언제나 환영합니당. 😊