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

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

소스결과 5064 KB / 84 ms

언어 C++ 17

출처 Baekjoon

분류 문자열 처리, 이진 탐색

 

설명

포켓몬 마스터 다솜이가 오박사가 주려는 도감을 탈 수 있도록 도와주자.

 

처음 문제를 봤을 때는 트라이를 이용해 문제를 해결 할 방법을 떠올렸다.

구성해서 돌려본 결과는 메모리초과, 각각의 경우마다 자식노드가 26가지 가능하고, 최대 깊이가 20이기에 어느정도 예상은 했지만, 결과는 예상대로였다.

 

문제에 있어 딱히 어려운 알고리즘은 없다. 입력된 포켓몬을 정렬한 후, 포켓몬 이름이 들어왔을 때, 번호를 출력해주면 된다. 다만, 포켓몬을 정렬하는 과정에서 입력된 번호가 바뀌기 때문에, 기존 번호를 저장하고 있는 구조체를 만들어서 정렬해준다.

 

알고리즘

1. 포켓몬을 입력받는다.

2. 포켓몬을 이름 순서대로 정렬해준다.

3. 숫자가 들어온 경우 번호 - 1 번의 인덱스 값을 출력해준다.

4. 포켓몬 이름이 들어온 경우 정렬된 배열에서 이분탐색을 통해 찾은 후, 구조체의 원래 번호를 출력해준다.

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N_MAX = 100000;
const short ALPHA_MAX = 26;
const short STR_MAX = 21;

struct PokeData {
	char* data;
	int number;

	PokeData() {};
	PokeData(char* data, int num) : data(data), number(num) {};
};

int n, m;
vector<PokeData> vec_poke;
char pokemons[N_MAX][STR_MAX];

bool cmp(const PokeData& p1, const PokeData& p2) {
	int pos = 0;
	while (p1.data[pos] != '\0' && p2.data[pos] != '\0') {
		if (p1.data[pos] > p2.data[pos])
			return false;
		else if (p1.data[pos] < p2.data[pos])
			return true;
		pos++;
	}

	return p1.data[pos] == '\0' ? true : false;
}

bool c_cmp(const char* c1, const char *c2) {
	int pos = 0;
	while (c1[pos] != '\0' && c2[pos] != '\0') {
		if (c1[pos] > c2[pos])
			return false;
		else if (c1[pos] < c2[pos])
			return true;
		pos++;
	}

	return c1[pos] == '\0' ? true : false;
}

int findPoke(char name[STR_MAX]) {
	int left = 0;
	int right = n - 1;

	while (left <= right) {
		int middle = (left + right) / 2;
		if (c_cmp(vec_poke[middle].data, name))
			left = middle + 1;
		else
			right = middle -1;
	}

	return vec_poke[right].number;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;

	vec_poke.resize(n);

	for (int i = 0; i < n; i++) {
		cin >> pokemons[i];
		vec_poke[i] = PokeData(pokemons[i], i + 1);
	}

	sort(vec_poke.begin(), vec_poke.end(), cmp);

	for (int j = 0; j < m; j++) {
		char input[STR_MAX] = {};
		cin >> input;

		if ('0' <= input[0] && input[0] <= '9')
		{
			int idx = atoi(input);
			cout << pokemons[idx - 1] << '\n';
		}
		else
		{
			cout << findPoke(input) << '\n';
		}
	}

	return 0;
}