[백준 13975번] 파이썬, c++ - 파일 합치기 3

백준 13975 - 파일 합치기 3

시간 제한 2초, 메모리 제한 512MB

# 조건

• 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다.
• 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다.
• 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다.
• 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.
  • 예를 들어, C1, C2, C3, C4가 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자.
  • 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다.
  • 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다.
  • 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다.
  • 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다.
  • 다른 방법으로 파일을 합치면 비용을 줄일 수 있다.
  • 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다.
  • 이때 필요한 총 비용은 70+80+150=300 이다.
• 소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.

입력

• 프로그램은 표준 입력에서 입력 데이터를 받는다.
• 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.
• 각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 1,000,000)가 주어진다.
• 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.

출력

• 프로그램은 표준 출력에 출력한다.
• 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.

# 접근 방법

• 문제의 핵심은 큰 수의 연산 횟수가 적어야 된다는 점이다.
• 따라서, 주어진 숫자들을 오름차순으로 정렬해준 후 아래 로직을 수행해준다.
  • while 문의 조건은 nums 배열의 길이가 1보다 클 때까지 수행한다.
  • heappop을 통해 가장 작은 수 2개를 출력하여 result에 더해주고, heappush를 통해 nums 배열에 다시 추가해준다.

# python

import sys
input = sys.stdin.readline
from heapq import heapify, heappop, heappush

T = int(input())
for _ in range(T):
    N = int(input())
    nums = list(map(int, input().split()))
    nums.sort()
    result = 0
    while len(nums) > 1:
        val1, val2 = heappop(nums), heappop(nums)
        val = val1 + val2
        result += val
        heappush(nums, val)    

    print(result) 

• 위의 풀이로는 4500ms의 풀이 시간이 나왔다.
• 시간을 더 줄여보기 위해 heap 모듈을 사용하는 것이 아닌 다른 방법으로 구현해주었다.
• 주어진 nums 배열을 정렬 한 리스트를 deque에 넣어주고, sq 이름의 deque를 하나 더 만들어 준다.
• while 문을 실행하는데 cnt => 전체 연산 횟수가 K-1보다 작을 때 까지만 돌려준다.
  • 모든 수를 더하는 전체 연산의 횟수는 K-1이기 때문이다.
• pop 함수를 실행하는데, fq가 비었다면 sq의 0번 값을, sq가 비었다면 fq의 0번 값을 temp에 더해준다.
  • 만약, 둘 다 값이 있다면 0번째 원소를 비교하여 더 작은 쪽을 temp에 더해준다.
• pop을 하여 새롭게 생성된 값을 sq에 추가해주고 cnt +=1 을 한다.

import sys
input = sys.stdin.readline
from collections import deque

def pop(f, s):
    temp = 0
    for _ in range(2):
        if not s:
            temp += f.popleft()        
        elif not f:
            temp += s.popleft()
        else:
            if f[0] <= s[0]:
                temp += f.popleft()
            else:
                temp += s.popleft()

    return temp


T = int(input())
for _ in range(T):
    K = int(input())
    nums = list(map(int, input().split()))
    nums.sort()
    cnt, result = 0, 0
    fq = deque(nums)
    sq = deque()
    while cnt < K - 1:
        val = pop(fq, sq)
        result += val
        sq.append(val)
        cnt += 1
    print(result)

• 위의 코드의 경우 2500ms의 시간이 나왔다..!!
• 라이브러리 사용이 편리하지만 시간 효율성을 항상 생각하고 더 빠른 풀이가 있는지 고민해보는 것이 중요한 것 같다.

# cpp

#include <iostream>
#include <queue>

using namespace std;
int T;

long long calc(priority_queue<long long, vector<long long>, greater<long long>>&q) {
    long long val1, val2, result = 0;
    while (q.size() > 1) {
        val1 = q.top();
        q.pop();
        val2 = q.top();
        q.pop();
        result += val1 + val2;
        q.push(val1 + val2);
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--) {
        priority_queue<long long, vector<long long>, greater<long long>> pq;
        int K, num;

        cin >> K;
        for (int i = 0; i < K; i++) {
            cin >> num;
            pq.push(num);
        }


        cout << calc(pq) << '\n';

    }

    return 0;
}