[Algorithm] 문자열 합치기 (Algospot – STRJOIN)

출처

• https://algospot.com/judge/problem/read/STRJOIN
• 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 (구종만)

난이도

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

문제

• 100개 이하의 String의 길이가 Input으로 주어진다. 주어진 String을 모두 합치고 싶다. String을 합치기 위해서는 두 개의 String 길이 만큼 For Loop을 돌아야 한다. 예를 들어 “st”, “ri”, “ng”가 Input으로 주어지면, 먼저 “stri”를 만들기 위해 총 4번의 For Loop을 돌아야 한다. “string”이라는 단어를 만들기 위해서는 총 10((2+2) + (4+2))번 For Loop을 돌아야 한다. 주어진 String을 모두 합치기 위해 For Loop을 돌아야 하는 최소 횟수를 찾는 문제이다.

후기

• 역시나 책을 읽고 있어서 탐욕법을 사용해서 문제를 해결해야 한다는 생각은 했다.
• 문제를 읽고 바로 Priority Queue를 사용해서 문제를 풀면 쉽게 풀릴 것 같았다. 그래서 Priority Queue를 만들어서 가장 짧은 문장을 먼저 합치고, 새롭게 만들어진 문자열을 Priority Queue에 추가하는 방법으로 문제를 해결하였다. Priority Queue를 너무 오랜만에 구현해서 실수를 몇 번 하였다. 지난번에도 비슷한 실수를 했는데 Priority Queue에 Pop을 할 때 Left Tree Node와 Right Tree Node가 Parent Node보다 값이 작을 경우 바꾸는 부분에서 항상 실수한다. Left와 Right Tree Node 모두가 Parent Node보다 작을 경우 Left와 Right Tree Node중 더 작은 수를 Parent로 만들어야 하는데 항상 이부분에서 실수한다.
• 문제를 풀고 책에 작성된 답안을 보니 동일한 답안이였다.

코드

• 탐욕법을 사용한 코드
• Github 주소: https://github.com/mkblog-cokr/algorithmCode
• 실행 시간: 1ms (제일 빠른 코드와 동일한 성능)

//MK: 탐욕방법을 사용한 문제 해결 코드
#include <stdio.h>

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

#define MAXSIZE 101

int inputList[MAXSIZE];

int treeSize;

//MK: Priority Queue (Tree)에 추가하는 부분
void insertIntoTree(int input) {
	inputList[treeSize] = input;
	int ptr = treeSize;
	treeSize++;
	while (ptr != 0) {
		int parent = (ptr - 1) / 2;
		if (inputList[parent] > inputList[ptr]) {
			int tmp = inputList[parent];
			inputList[parent] = inputList[ptr];
			inputList[ptr] = tmp;
			ptr = parent;
		}
		else {
			break;
		}
	}
}

//MK: Priority Queue에서 가장 작은 수를 Return하는 함수
int popFromTree() {
	treeSize--;
	int ret = inputList[0];
	inputList[0] = inputList[treeSize];
	inputList[treeSize] = 0;
	int ptr = 0;
	while (ptr < treeSize) {
		int lhs = ptr * 2 + 1;
		int rhs = ptr * 2 + 2;
		if ((inputList[lhs] < inputList[ptr] && lhs < treeSize) && (inputList[rhs] < inputList[ptr] && rhs < treeSize)) {
			if (inputList[lhs] < inputList[rhs] ) {
				int tmp = inputList[lhs];
				inputList[lhs] = inputList[ptr];
				inputList[ptr] = tmp;
				ptr = lhs;
			}
			else{
				int tmp = inputList[rhs];
				inputList[rhs] = inputList[ptr];
				inputList[ptr] = tmp;
				ptr = rhs;
			}
		}
		else if (inputList[lhs] < inputList[ptr] && lhs < treeSize) {
			int tmp = inputList[lhs];
			inputList[lhs] = inputList[ptr];
			inputList[ptr] = tmp;
			ptr = lhs;
		}
		else if (inputList[rhs] < inputList[ptr] && rhs < treeSize) {
			int tmp = inputList[rhs];
			inputList[rhs] = inputList[ptr];
			inputList[ptr] = tmp;
			ptr = rhs;
		}
		else {
			break;
		}
	}
	return ret;
}

int main() {
	//freopen("input.txt", "r", stdin);
	int testCase = 0;
	scanf("%d", &testCase);
	for (int m = 0; m < testCase; m++) {
		treeSize = 0;
		int tmpSize;
		scanf("%d", &tmpSize);
		for (int i = 0; i < tmpSize; i++) {
			int tmp;
			scanf("%d", &tmp);
			insertIntoTree(tmp);
		}
		int result = 0;
		//MK: 탐욕법으로 문제를 해결하는 부분 (함수를 만들기에 너무 짧음)
		while (treeSize > 1) {
				int tmp0 = popFromTree();
				int tmp1 = popFromTree();
				result += (tmp0 + tmp1);
				insertIntoTree((tmp0 + tmp1));
		}
		printf("%d\n", result);
	}
	return 0;
}