[코딩테스트][백준] 🔥 백준 2461번 "대표 선수" 문제: Python과 Java로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 60분

import heapq

n,m=map(int,input().split())
classes=[]
for _ in range(n):
    arr=list(map(int,input().split()))
    heapq.heapify(arr)
    classes.append(arr)
answer=1e9
max_value=-1
q=[]
for i in range(n):
    k=heapq.heappop(classes[i])
    heapq.heappush(q,(k,i))
    max_value=max(k,max_value)
while True:
    now=heapq.heappop(q)
    if answer>abs(now[0]-max_value):
        answer=abs(now[0]-max_value)
    if not classes[now[1]]:
        break
    tmp=heapq.heappop(classes[now[1]])
    max_value=max(tmp,max_value)
    heapq.heappush(q,(tmp,now[1]))
print(answer)

🕒 Java 풀이시간: 60분

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) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(st.nextToken());
        List<PriorityQueue<Long>> classes = new LinkedList<PriorityQueue<Long>>();
        for(int i=0;i<n;i++){
            PriorityQueue<Long> pq=new PriorityQueue<>();
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                pq.add(Long.parseLong(st.nextToken()));
            }
            classes.add(pq);
        }
        long answer=Long.MAX_VALUE;
        long max_value=-1;
        PriorityQueue<long[]> pq=new PriorityQueue<>((a,b)->Long.compare(a[0],b[0]));
        for(int i=0;i<n;i++){
            long cgp=classes.get(i).remove();
            long[] arr=new long[2];
            arr[0]=cgp;
            arr[1]=i;
            pq.add(arr);
            if(max_value<cgp){
                max_value=cgp;
            }
        }        
        while(true){
            long[] now=pq.remove();
            if(answer>Math.abs(now[0]-max_value)){
                answer=Math.abs(now[0]-max_value);
            }
            if(classes.get((int)now[1]).isEmpty()){
                break;
            }
            long tmp=classes.get((int)now[1]).remove();
            if(tmp>max_value){
                max_value=tmp;
            }
            pq.add(new long[]{tmp,now[1]});
            
        }
        System.out.println(answer);
    }
        
}

문제 해결 과정 🤔

처음에는 단순히 각 배열을 우선순위 큐로 받은 다음, 모든 큐 중에서 가장 작은 값을 가진 큐에서 꺼내는 식으로 진행했습니다. 그 후 각 peek을 전부 순회하면서 최대, 최소를 구하는 방법을 사용했지만, 시간초과가 발생했습니다.

개선된 해결책 💡

그래서 새로운 해결책을 생각해냈습니다. 작은 값 순으로 필요하기 때문에 우선순위 큐에 넣는 것은 적절한 방법이라고 판단했습니다. 하지만 같은 반끼리 비교해버릴 수도 있다는 문제가 있었습니다.

이를 해결하기 위해 작은 값 순으로 넣는 대신, 반과 함께 묶어서 넣기로 했습니다. 이렇게 하면 작은 값 순으로 나오면서 다음 값을 큐에 넣을 때, 꺼낸 반에서 찾아서 넣을 수 있습니다. 따라서 같은 반끼리 충돌할 일을 피할 수 있습니다.

다만 최댓값의 경우, 현재의 최댓값이 아니라면 방금 꺼낸 값이 되므로, 계속해서 갱신해 주어야 합니다.

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