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

 알고리즘 연습이 소홀해져서 오랜만에 백준을 풀다가 특이한 제목의 문제라서 한 번 시도했다가 꽤 오래 풀었다. 문제 자체는 쉬운데 시간제한을 맞춰줘야 하기 때문에 정렬과 탐색을 적절히 써야하는 문제다.

과도한 컨셉의 폐혜

입출력 예시

정답코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct pocketmon {
	char name[21];
	int i;
};

int isInteger(char *);
int pocketmonSearch(struct pocketmon *, char *, int, int);
void quickSort(struct pocketmon *, int, int);
int inPlacePartition(struct pocketmon *, int, int, int);

int main() {

	int n, m;

	struct pocketmon *pocketmon;
	struct pocketmon *tmp;

	int i;

	char search[21];

	scanf("%d %d", &n, &m);

	pocketmon = (struct pocketmon *)malloc(sizeof(struct pocketmon) * n);
	tmp = (struct pocketmon *)malloc(sizeof(struct pocketmon) * n);

	for (i = 0; i < n; i++) {
		scanf("%s", pocketmon[i].name);
		pocketmon[i].i = (i + 1);

		strcpy(tmp[i].name, pocketmon[i].name);
		tmp[i].i = (i + 1);
	}

	quickSort(pocketmon, 0, n - 1);

	for (i = 0; i < m; i++) {
		scanf("%s", search);

		if (isInteger(search)) {	// 입력이 숫자일 시
			printf("%s\n", tmp[atoi(search) - 1].name);
		}
		else {						// 입력이 이름일 시
			printf("%d\n", pocketmonSearch(pocketmon, search, 0, n - 1));
		}

	}

	return 0;

}

int isInteger(char *str) {

	int i;

	for (i = 0; str[i]; i++) {
		if (!('0' <= str[i] && str[i] <= '9')) return 0;
		else return 1;
	}

}

int pocketmonSearch(struct pocketmon *pocketmon, char *search, int l, int r) {

	int m = (l + r) / 2;

	if (strcmp(pocketmon[m].name, search) == 0)
		return pocketmon[m].i;
	else if (strcmp(pocketmon[m].name, search) < 0)
		return pocketmonSearch(pocketmon, search, m + 1, r);
	else
		return pocketmonSearch(pocketmon, search, l, m - 1);

	return 0;

}

void quickSort(struct pocketmon *po, int l, int r) {

	int a, b;

	if (l >= r)
		return;

	a = b = inPlacePartition(po, l, r, r);

	quickSort(po, l, a - 1);
	quickSort(po, b + 1, r);

}

int inPlacePartition(struct pocketmon *po, int l, int r, int k) {

	struct pocketmon p;
	struct pocketmon tmp;

	int i, j;

	p = po[k];


	tmp = po[k];
	po[k] = po[r];
	po[r] = tmp;

	i = l;
	j = r - 1;

	while (i <= j) {
		while (i <= j && (strcmp(po[i].name, p.name) <= 0)) {
			i++;
		}
		while (j >= i && (strcmp(po[j].name, p.name) >= 0)) {
			j--;
		}
		if (i < j) {
			tmp = po[i];
			po[i] = po[j];
			po[j] = tmp;
		}
	}

	tmp = po[i];
	po[i] = po[r];
	po[r] = tmp;

	return i;

}

코드가 너무 길어! 아악 내눈!

코드설명

1.  포켓몬 구조체를 만든다. 포켓몬의 이름과 포켓몬이 입력된 순서가 멤버변수로 존재한다.

2.  n (입력받을 포켓몬의 수), m(검색할 포켓몬의 수), pocketmon (이름으로 검색 시 사용할 포켓몬 배열), tmp (숫자로 검색 시 사용할 포켓몬 배열)을 선언한다. n과 m을 받고 pocketmon과 tmp를 동적할당 한다. 

 * 포켓몬 구조체 배열을 두개로 나눈 이유는 검색시간을 최소화 하기 위해서이다. 문자열 배열 하나로 해결했을때는 금방 했는데, 시간초과가 떴다! 아마 테스트케이스에 검색 시간이 최악의 경우로 걸리는 경우가 있는 것 같다. 

 * 검색을 n과 같은 횟수로 하고 항상 n번째에 있는 포켓몬 이름만 검색하면 무려 O(n^2)이다. 

 * 포켓몬 이름 검색의 시간복잡도를 최소화 하기 위해 (제자리)퀵 정렬을 사용했고, 퀵 정렬을 하면 인덱스 번호가 흐트러지기 때문에 구조체를 사용해 입력 당시 순서를 저장했다. 퀵 정렬의 기준원소는 항상 r번째 (분할 된 인덱스 중 가장 오른쪽)으로 했다.

 * 퀵 정렬 사용을 위해 구조체를 정렬하면, 숫자로 검색 했을 때 또 위와 같이 O(n^2)의 경우에 걸릴 수 있기 때문에, 입력 당시 순서와 똑같이 보존할 배열을 하나 더 만들었다. (tmp)

3. 포켓몬의 이름을 입력받는다. pocketmon과 tmp에 이름과 입력받을 당시 순서를 저장한다. (tmp에 순서저장은 생략해도 된다.)

4. pocketmon 배열을 퀵 정렬한다.

5. m번 만큼 검색할 포켓몬의 이름 혹은 순서를 입력받는다. 순서(숫자)를 입력받았을 땐 tmp를 이용해 O(1)의 시간만에 검색하고, 이름을 입력받았을 땐 이진탐색을 이용해 O(log n)의 시간만에 검색한다.

6. 최종적으로, 퀵 정렬에 O(n * log n)의 시간이 걸리니 총 프로그램의 시간복잡도는 O(n * log n)이다. 시간 제한을 통과할 수 있다.

문제 풀기 참 힘들당.

더 짧고 효율적으로 풀 방법을 생각해야겠다.