[알고스팟] STRJOIN - 문자열 합치기 (C++)

문제

 

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

algospot.com :: STRJOIN

 

풀이

 

종만북 난이도: 중

 

난이도는 중인 그리디 문제이지만 C++ STL의 우선순위 큐(priority_queue)와 같은 컨테이너 라이브러리를 안다면 쉽게 해결할 수 있다.

 

일단 예를 들어 4개의 문자열(str1, str2, str3, str4)을 순서대로 합친다고 생각해보자.

첫번째로 합쳐진 문자열의 길이는 len1(str1+str2), 두번째는 len2(len1+ str3), 마지막으로 len3(len2 + str4)가 있다.

 

여기서 총 합체 비용은 아래와 같다.

len1 + lne2 + len3 = (str1+str2) + (len1+ str3) + (len2 + str4)

=  (str1+str2) + (str1+str2+ str3)+  (str1+str2+ str3 + str4)

=  3*str1 + 3*str2 + 2* str3 + str4 

 

문자열이 n개일 때도 결국 아래의 비용을 같는다. (물론 이미 합친 문자열을 먼저 다시 합칠 수는 있지만 순서대로만 합친다고 가정하자.)

(n-1)*str1 + (n-1)*str2 + (n-2)*str3 + ... + 1*str_n

 

따라서 먼저 합쳐진 문자열의 길이가 가장 많이 연산에 포함됨을 알 수 있다.

 

즉, 합칠 문자열은 문자열 중에서 가장 작은 두 값을 선택하여 합하는 것이 항상 최선이다.

위의 가정과 달리 합쳐진 문자열의 크기가 기본 문자열들보다 큰 경우도 있다.

하지만 이런 경우도 합쳐진 여부와 관계없이 가장 작은 두 값을 항상 선택하여, 만들어내는 문자열의 길이를 작게 것이 최소 비용을 만든다.

 

해당 알고리즘을 구현할때 우선순위 큐(priority_queue)를 사용하면 매우 편리하다.

우선순위큐는 항상 저장된 값들을 O(nlogn)의 복잡도로 정렬하여 유지한다.

우리가 항상 작은 두 값을 얻기위해서는 오름차순으로 정렬된 priority_queue에서 가장 위의 두 값 값들을 가져오면 된다.

두 값을 꺼낸 후 두 값을 더한 값(합쳐진 문자열의 길이)을 다시 push 해주는 연산을 priority_queue의 크기가 1이될 때까지 반복해주자.

 

코드