[코딩테스트][백준] 🔥 백준 13975번 "파일 합치기 3" 문제: Python과 Java로 완벽 해결하기! 🔥

문제 링크

https://www.acmicpc.net/problem/13975

🕒 Python 풀이시간: 5분

import heapq

for _ in range(int(input())):
    k=int(input())
    arr=list(map(int,input().split()))
    arr.sort()
    heapq.heapify(arr)
    total=0
    while len(arr)>1:
        a=heapq.heappop(arr)
        b=heapq.heappop(arr)
        total+=a+b
        heapq.heappush(arr,a+b)
    print(total)

🕒 Java 풀이시간: 10분

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int tc=sc.nextInt();
        for(int i=0;i<tc;i++){
            int n=sc.nextInt();
            long total=0;
            PriorityQueue<Long> pq=new PriorityQueue<>();
            for(int j=0;j<n;j++)
                pq.offer(sc.nextLong());
            // for(int j=0;j<n;j++)
            //     System.out.println(pq.poll());
            while(pq.size()>1){
                long a=pq.poll();
                long b=pq.poll();
                total+=(a+b);
                pq.offer(a+b);
            }
            System.out.println(total);
        }
    }
}

🐍 우선순위 큐를 활용한 문제 해결

우선순위 큐는 O(N log N)의 시간복잡도를 가지기 때문에 데이터 양과 비교했을 때, 100만 개의 데이터는 약 2초 이내에 처리할 수 있을 것으로 예상됩니다.

🔍 문제 접근 방법 🔍

모든 데이터를 큐에 넣고, 꺼내면서 두 개의 수의 합을 결과에 더하고, 그 합을 다시 큐에 넣는 방식으로 진행합니다. 이 과정을 반복하다가 마지막에 남은 한 개의 값은 결과에 포함하지 않습니다.

🐍➡️☕ 파이썬에서 자바로의 전환 🐍➡️☕

파이썬에서는 이 문제를 쉽게 해결할 수 있었지만, 자바로 변환하는 과정에서 자료형에 대한 신경을 덜 썼습니다. 수의 크기가 long까지 클 수 있기 때문에, 큐에 들어가는 모든 수뿐만 아니라 최종 결과값도 Long 타입으로 바꾸는 것이 중요했습니다.

이렇게 Python과 Java로 백준의 "파일 합치기 3" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊