[python] algospot STRJOIN 문제풀이

문제

 

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

 

위의 strcat 함수를 이용해 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 의 비용이 필요합니다.

-> 문제 링크 : https://www.algospot.com/judge/problem/read/STRJOIN

algospot.com :: STRJOIN

 

문제풀이

위 함수를 사용하면 두 문자열을 합칠 때 두 문자열 길이의 합만큼 비용이 소요된다. 두 문자열을 합쳐가는 과정을 X번 반복하게 되는거니까 두 문자열을 합치는 비용을 계속해서 최소로 사용하면 전체 비용도 최소가 된다고 유추할 수 있다.

정확한 판단을 위해서는 그리디가 성립하는 두가지 조건을 검사해봐야 하지만 여기서는 생략하겠다.

예제 문제를 손으로 풀다보면 현재 합쳐야 하는 문자열 중에서 길이가 가장 작은 두 문자열을 합치면 비용이 최소가 되는 것을 확인할 수 있다. 

 

이 문제는 heap을 사용해 풀 수 있다. heap의 삽입과 삭제는 O(logN)이기에 N번 반복한다해도 시간복잡도는 O(NlogN)이다.

문자열 개수가 100개 이하기에 충분히 처리할 수 있다.

합쳐야 하는 문자열의 길이를 모두 heap으로 넣는다.

반복문을 통해 최소값을 갖는 두 문자열 길이를 뽑아내서 더한 뒤 다시 삽입하는 과정을 반복한다.

이때 뽑아낸 두개의 값을 더하는 과정이 strcat 함수를 처리할 때 발생하는 비용이다.

이를 반복하다보면 숫자가 한개만 남는 상황이 발생하는데 그 숫자가 모든 문자열이 합쳐진 상태를 의미하게 된다.

문자열이 모두 합쳐질 때까지 발생한 비용을 다 더하면 최소 비용이 나오게 된다.

 

코드

import sys
import heapq

# 1개
T = int(sys.stdin.readline().rstrip())

for _ in range(T) :

    N = int(sys.stdin.readline().rstrip())
    lengths = list(map(int,sys.stdin.readline().rstrip().split()))

    heapq.heapify(lengths)
    answer = 0

    for _ in range(N-1) :
        a = heapq.heappop(lengths)
        b = heapq.heappop(lengths)

        heapq.heappush(lengths, a+b)
        answer += a+b

    print(answer)

 

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.