[Algorithm] pDNA (Algospot – PDNA)

문제 출처

  • https://algospot.com/judge/problem/read/PDNA

문제 난이도

  • (하) – 중 – 상 – 최상 – 풀지 못함

문제 설명 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)

  • 입력으로 최대 10개의 단어를 주면, 단어들을 조합하여 하나의 단어를 만들어야 한다. 만들어진 단어가 어느 방향에서 읽어도 같으면 pDNA라고 한다. 예를 들어 ABCD는 pDNA가 아니지만, ABBA는 pDNA이다. 만약 여러 개의 pDNA가 존재하면 사전 순으로 앞에 오는 것을 출력하면 된다. (pDNA라는 말은 실제로는 존재하지 않는 단어라고 한다)

후기

  • 최대 10개의 단어라서 가능한 모든 조합을 만들어보는 Recursive 함수를 작성하였다. 그리고 실행을 하니 문제가 해결하였다.
  • 조금 어려웠던 부분은 사전 순으로 결과를 정리하는 부분이다. 조합한 단어가 pDNA이면, 기존의 답과 비교하여 사전 순으로 앞에 있으면 답을 새롭게 생성된 단어로 변경하는 방법을 선택하였다. 사전 순으로 비교하는 부분에서 비교문을 제대로 사용하지 못하여서 조금 시간이 걸렸다. 무조던 앞에 존재하는 단어가 사전순으로 앞에 있으면 뒤 단어의 조합을 확인할 필요가 없지만, 실수로 계속 비교하는 코드를 작성하여 디버깅에 조금 시간이 걸렸다.
  • 추가: Recursive 함수에 가지치기 같은 방법을 추가하면 실행 시간을 줄일 수 있을 것 같은데 아직은 정확한 방법이 생각나지 않는다. 현재 “프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략” 책을 읽고 있는데 아마 본 문제는 동적 계획법 테크닉을 사용하여 문제를 풀어야 하는 것 같다. 아직 그 부분까지 읽지 않고 문제를 풀어서 아마 최적의 답안은 아닐 것으로 판단된다.

코드

#include <stdio.h>

//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable:4996)

#define MAXSIZE 101

#define TRUE 1
#define FALSE 0

char input[10][MAXSIZE];
int visitedMap[10];
char result[MAXSIZE];
char finalResult[MAXSIZE];
int inputSize;
int end;

void init() {
	for (int i = 0; i < inputSize; i++) {
		visitedMap[i] = 0;
	}
	for (int i = 0; i < MAXSIZE; i++) {
		finalResult[i] = '\0';
	}
}

int isItPDna() {
	int endPtr = end - 1;
	int beginPtr = 0;
	while (1) {
		if (endPtr <= beginPtr) {
			break;
		}
		if (result[beginPtr] != result[endPtr]) {
			return FALSE;
		}
		endPtr--;
		beginPtr++;
	}
	return TRUE;
}

void insertIntoResult(int strId) {
	int i = 0;
	while (input[strId][i] != '\0') {
		result[end] = input[strId][i];
		end++;
		i++;
	}
	result[end] = '\0';
}

//MK: 가지치기를 해서 시간을 줄여 볼려고 시도한 부분 (정상 동작 X)
//MK: 기존 답의 앞의 단어가 작으면 뒤에는 비교를 할 필요 없으나, 앞의 여부와 상관 없이 뒤 문자를 비교하다 보니 사전 순으로 더 앞에 있음에도 불구하고 잘못된 값을 리턴함
//MK: 수정이 필요함.
/*
int isItSmaller(int strId) {
	int i = 0;
	int ptr = end;
	int ret = FALSE;
	if (finalResult[ptr] == '\0') {
		ret = TRUE;
	}
	else{
		while (input[strId][i] != '\0') {
			if (finalResult[ptr] > input[strId][i]) {
				ret = TRUE;
				break;
			}
			ptr++;
			i++;
		}
	}
	return ret;
}*/

void findFinalResult() {
	int needChange = FALSE;
	if (finalResult[0] == '\0') {
		needChange = TRUE;
	}
	else {
		int i = 0;
		while (finalResult[i] != '\0') {
			if (finalResult[i] > result[i]) {
				needChange = TRUE;
				break;
			}
			else if (finalResult[i] != result[i]){
				needChange = FALSE;
				break;
			}
			i++;
		}
	}
	if (needChange == TRUE) {
		int i = 0;
		while (result[i] != '\0') {
			finalResult[i] = result[i];
			i++;
		}
	}
}

//MK: 단순히 모든 탐색(Brute Force Search)을 사용한 문제 해결 방법
void findPDna(int numStr) {
	if (numStr == inputSize) {
		if (isItPDna() == TRUE) {
			findFinalResult();
		}
		return;
	}
	for (int i = 0; i < inputSize; i++) {
		//MK: isItSmaller 사용할 수 없음.
		//if (visitedMap[i] == 0 && isItSmaller(i) == TRUE) { 
		if (visitedMap[i] == 0) {
			visitedMap[i] = 1;
			int tmp = end;
			insertIntoResult(i);
			findPDna(numStr + 1);
			end = tmp;
			visitedMap[i] = 0;
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);

	int testCase;
	scanf("%d", &testCase);
	for (int m = 1; m <= testCase; m++) {
		end = 0;
		scanf("%d", &inputSize);
		init();
		for (int i = 0; i < inputSize; i++) {
			scanf("%s", &input[i]);
		}
		findPDna(0);
		printf("%s\n", finalResult);
	}
	return 0;
}

 

Leave a Comment