백준 2461 : 대표 선수

문제 링크

n 개의 크기 m 짜리 정수 배열이 있을 때, 각 배열에서 하나씩 수를 골라서 n 개의 수들의 최댓값과 최솟값의 차이를 가장 작게 하는 것이 문제이다.

priority_queue를 이용하여 해결하였다.

brute 하게 풀면 모든 값에 대해 그 값이 최솟값일 때 n 개의 배열을 순회하면서 나올 수 있는 최댓값을 구해 주어서 해결할 수 있지만, O(n^3logn)이 걸리고, 이는 n<=1000이기 때문에 불가능하다.

따라서 지금까지 본 수들 중 가장 큰 수를 저장하는 curmax와 우선순위 큐를 이용하였다. 우선순위 큐에는 처음에 각 팀에서 가장 작은 수를 push 해 준 다음, top과 curmax의 차이를 기록하고, top이 소속된 팀에서 그다음 작은 수를 우선순위 큐에 push 함으로써 해결하였다.(소스코드 for(int i =0;i<n*m-n;i++)부터, 42줄)

결과적으로 모든 값에 대해 그 값이 최솟값일 때의 답을 구한 것은 brute 한 방법에서의 아이디어와 크게 다르지 않지만, 우선순위 큐를 이용하여 정보를 저장함으로써 시간 복잡도를 O(n^2logn)까지 줄일 수 있었다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

typedef pair<int,int> pii;
const int INF = 21 * 1e8;

int n,m;
vector<vector<int>> vec;
vector<int> idx;
priority_queue<pii,vector<pii>,greater<pii>> pq;

int main()
{
    scanf("%d %d",&n,&m);

    vec = vector<vector<int>>(n,vector<int>(m));
    idx = vector<int>(n,0);

    for(int i = 0;i<n;i++)
    {
        for(int j =0;j<m;j++)
        {
            scanf("%d",&vec[i][j]);
        }
    }

    int curmax = 0;
    for(int i =0;i<n;i++)
    {
        sort(vec[i].begin(),vec[i].end());
        curmax = max(curmax,vec[i][0]);
        pq.push({vec[i][0],i});
    }

    int ans = INF;
    
    for(int i =0;i<n*m-n;i++)
    {
        pii cur = pq.top();
        int minidx = cur.second;
        ans = min(ans,curmax - cur.first);

        if(idx[minidx] == n-1) break;
        else 
        {
            pq.pop();
            idx[minidx]++;
            curmax = max(curmax,vec[minidx][idx[minidx]]);
            pq.push({vec[minidx][idx[minidx]],minidx});
        }
    }

    printf("%d",ans);
    return 0;
}