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

www.algospot.com

[ALGOSPOT] 알고스팟 STRJOIN 문자열 합치기

(C++, Python)

(글쓴날 : 2020.04.30)

 

---

* ALGOSPOT, 알고스팟 STRJOIN 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 STRJOIN 문자열 합치기

---

1) 문제

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

algospot.com :: STRJOIN

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

문자열들의 길이가 N개만큼 주어질 때, C언어의 strcat() 함수의 원리로 각 문자열들을 순서에 상관없이 합치는 최소 비용을 구하는 문제입니다.

strcat() 함수의 비용은 합칠 두 문자열의 길이의 합과 같습니다.

 

저의 경우, 우선순위 큐를 이용한 그리디를 적용하였으며, C++과 Python을 사용했습니다.

우선순위 큐의 내부는 Min Heap으로 구현하여 최소 길이를 항상 반환할 수 있게 끔 만들었고, 가장 짧은 길이의 문자열들을 합치고 비용을 저장한 뒤, 다시 우선순위 큐에 넣는 식으로 최소비용을 구해 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
struct cmp
{
    bool operator()(int oldValue, int newValue)
    {
        return oldValue > newValue;
    }
};
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int ans = 0;
    int c = 0;
    cin >> c;
 
    int n = 0;
    priority_queue<int, vector<int>, cmp> strLength;
    int inputLength = 0;
    int length1 = 0;
    int length2 = 0;
 
    while (c--)
    {
        cin >> n;
        ans = 0;
        strLength = priority_queue<int, vector<int>, cmp>();
 
        for (int i = 0; i < n; i++)
        {
            cin >> inputLength;
            strLength.push(inputLength);
        }
 
        for (int i = 0; i < n - 1; i++)
        {
            length1 = strLength.top();
            strLength.pop();
            length2 = strLength.top();
            strLength.pop();
 
            ans += length1 + length2;
            strLength.push(length1 + length2);
        }
 
        cout << ans << "\n";
    }
 
    return 0;
}

---

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
c = int(input())
 
for _ in range(c):
    n = int(input().rstrip())
    strLength = []
    ans = 0
 
    for length in map(int, input().split()):
        heapq.heappush(strLength, length)
    
    for _ in range(n - 1):
        length1 = heapq.heappop(strLength)
        legnth2 = heapq.heappop(strLength)
 
        ans += length1 + legnth2
        heapq.heappush(strLength, length1 + legnth2)
    
    print(ans)

---