[알고리즘] C++ 백준 2461 대표 선수

백준 2461

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

2461번: 대표 선수

 

풀이 전 나의 생각

KOI 중학교의 학급 N개와 각 학급의 학생 수 M이 주어질 때,

각 학급의 대표의 최댓값과 최소값의 차이가 최소가 되는 경우를 구해야 한다.

 

조건

- 1 ≤ N, M ≤ 1,000

- 능력치는 0이상 109이하

 

과정

N과 M이 1000개로 주어졌다고 가정 했을 때 단순 for문을 이용해서
모든 경우를 탐색할 시 1000 ^ 1000의 횟수가 나오기 때문에
시간 제한을 맞추지 못한다.

 

따라서 포인터와 우선순위 큐 개념을 사용하여 풀이를 진행했다.

 

이 문제에서 중요한 것은 모든 경우를 탐색할 필요가 없이
학급에서 선발한 대표 중 최대값과 최소값만 구해서 결과를 비교하면 된다는 것이다.

 

과정은 다음과 같다.

1. 각 학급의 정보를 내림차순으로 정렬 한다.

2. 각 학급의 첫 대표 학생을 기준으로 최소값과 최대값 구한다.

3. 최대값 - 최소값을 진행하여 결과값을 갱신한다.

4. 다음 비교를 위해 현재 최대값 학급의 다음 최대값을 우선순위 큐에 삽입한다.

 

예를 들어

12 16 67 43
7 17 68 48
14 15 77 54
의 학급이 있다고 가정할 때,

67 43 16 12
68 48 17 7
77 54 15 14
로 정렬 되고

초기 대표의 최대 - 최소 (77- 67)을 구해준 후,
현재 최대값 학급의 다음 최대값 54를 우선순위 큐에 넣어준다.
다음으로는 (68 - 54)가 진행되고 68의 학급의 다음 최대값 48이 우선순위 큐에 삽입된다.

앞서 말했듯이, 선택된 학급의 모든 학생을 탐색하는 것이 아닌, 

학급 대표의 최소, 최대만 구하면 된다. 

따라서 최소, 최대를 갱신해가며 최적의 값을 찾아 결과를 갱신 해주면 된다. 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>> c_skill(1001);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	priority_queue<pair<int, pair<int, int>>> pq;

	int N, M, min_num = INT_MAX, result = INT_MAX;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			int skill;
			cin >> skill;
			c_skill[i].push_back(skill);
		}
	}

	for (int i = 0; i < N; i++)
	{
		//각 학급 내림 차순 정렬
		sort(c_skill[i].begin(), c_skill[i].end(), greater<int>());
		//첫 대표 학생의 최소값
		min_num = min(min_num, c_skill[i][0]);
		//첫 대표 학생의 정보를 우선순위 큐에 삽입 (큐에 삽입된 대표 N명을 통해 최대값을 얻기 위해)
		pq.push(make_pair(c_skill[i][0], make_pair(i, 0)));
	}

	while (!pq.empty())
	{
		//우선순위 큐에 삽입된 대표 학생의 최대값 
		int max_num = pq.top().first;
		//반
		int max_idx = pq.top().second.first;
		//순서
		int max_arridx = pq.top().second.second;
		pq.pop();

		//큐의 대표 학생의 최대값 - 최소값으로 결과 갱신
		result = min(result, max_num - min_num);

		// 순서가 지정된 학급의 크기 M을 넘어가면 벗어남
		if (max_arridx + 1 == M) break;

		//다음 최소, 최대 비교를 위해 최소값 갱신
		min_num = min(min_num, c_skill[max_idx][max_arridx + 1]);
		//다음 최소, 최대 비교를 위해 현 최대값 대표 학생의 다음 대표 학생 삽입
		pq.push(make_pair(c_skill[max_idx][max_arridx + 1], make_pair(max_idx, max_arridx + 1)));
	}

	cout << result;
}