출처
- 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; }