[AlgoSpot][Python] 문자열 합치기

📒 문제 설명

🔖 https://www.algospot.com/judge/problem/read/STRJOIN

📖 문제
프로그래밍 언어 C의 큰 문제점 중 하나는 언어 차원에서 문자열 변수형을 지원하지 않는다는 것입니다. C에서는 문자 배열로 문자열을 표현하되 \0 (NULL) 로 문자열의 끝을 지정하는데, 이래서는 문자열의 길이를 쉽게 알 수 있는 방법이 없기 때문에 여러 가지 문제가 발생하게 됩니다.

void strcat(char* dest, const char* src) {
 // dest 의 마지막 위치를 찾는다
 while(*dest) ++dest;
 // src 를 한 글자씩 dest 에 옮겨 붙인다
 while(*src) *(dest++) = *(src++);
 // 문자열의 끝을 알리는 \0 을 추가한다
 *dest = 0;
}

이런 문제 중 하나로 문자열을 조작하는 함수들의 동작 시간이 불필요하게 커진다는 것이 있습니다. 앞에 주어진 함수 strcat() 은 문자열 dest 뒤에 src를 붙이는 함수인데, 실행 과정에서 반복문을 두 문자열의 길이를 합한 만큼 수행해야 합니다. 이 함수를 사용해 두 개의 문자열을 합치는 비용은 두 문자열의 길이의 합이라고 합시다.

이 함수를 이용해 n 개의 문자열을 순서와 상관없이 합쳐서 한 개의 문자열로 만들고 싶습니다. 순서가 상관 없다는 말은 {al,go,spot}을 spotalgo로 합치든 alspotgo로 합치든 상관 없다는 의미입니다. 그러나 문자열을 합치는 순서에 따라 전체 비용이 달라질 수 있습니다. 예를 들어 먼저 al과 go를 합치고 (2+2=4), 이것을 spot과 합치면 (4+4=8) 총 12의 비용이 들지만 al과 spot을 합치고 (2+4=6) 이것을 다시 go에 합치면 (6+2=8) 총 14의 비용이 필요합니다.

n 개의 문자열들의 길이가 주어질 때 필요한 최소 비용을 찾는 프로그램을 작성하세요.

✍ 입력
입력의 첫 줄에는 테스트 케이스의 수 c (c <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 문자열의 수 n (1 <= n <= 100) 이 주어지며, 다음 줄에는 n 개의 정수로 각 문자열의 길이가 주어집니다. 각 문자열의 길이는 1,000 이하의 자연수입니다.

💻 출력
각 테스트 케이스마다 한 줄에 모든 문자열을 합칠 때 필요한 최소 비용을 출력합니다.

---

✏️ 풀이 과정

📝 접근 및 이론적 배경

• 그리디 알고리즘을 사용한 예인 허프만 코드를 각색한 문제로 소개되었다.

🔎 허프만 코드 (Huffman's Code)

• 특정 문자열을 구성하는 문자들을 빈도수를 활용하여 가변 길이 인코딩 테이블을 만드는 최적화 기법으로, 여러 압축 알고리즘에 활용된다.
  
  
• 자주 출현하는 글자는 더 짧은 패턴으로, 가끔 출현하는 글자는 더 긴 패턴으로 배당한다.

• 허프만 코드에서 트리를 생성하는 과정을 나타내어 보면, 이 문제와 연계성이 명확해진다.

• 합쳐서 생성된 문자열의 길이가 짧을 수록 해당 문자열의 끝을 탐색하기 위한 반복의 횟수가 줄어듦으로, 문자열의 길이가 짧은 순으로 정렬했다,

• 사용된 기존 문자열은 제거하고, 합쳐서 생성한 문자열은 str_len 에 새로 추가하여 문자열의 길이가 짧은 순으로 다시 정렬한다. 이후 str_len에 남은 문자열이 없을 때까지 이 과정을 반복한다.

• 매번 str_len을 정렬하는 대신, min 함수를 사용하여 str_len의 최솟값만 탐색하여 제거하는 방법이 실행 시간 면에서 유리한 것 같다.

✨ 소스 코드

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())
    str_len = list(map(int, input().split()))
    ans = 0

    while len(str_len) > 1:
        str_len.sort()
        popped = str_len.pop(0) + str_len.pop(0)
        ans += popped
        str_len.append(popped)

    print(ans)