[백준 2461] 대표 선수 (C++)

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

2461번: 대표 선수

2024 팀네이버 신입 공채 온라인 코딩테스트 문제 중 2번과 유사한 문제.

문제

---

KOI 중학교에는 N개의 학급이 있으며, 각 학급의 학생 수는 모두 M명으로 구성된다. 이 중학교에서는 체육대회에 새로운 종목의 경기를 추가하였다. 이 경기에 대해 모든 학생들은 저마다의 능력을 나타내는 능력치를 가지고 있으며, 이 능력치는 모든 학생이 서로 다르다.

이 경기는 한반에서 한 명의 대표선수를 선발하여 치른다. 경기의 형평성을 위하여, 각각의 반에서 대표로 선발된 모든 학생들의 능력치 중 최댓값과 최솟값의 차이가 최소가 되도록 선수를 선발하려고 한다. 예를 들어, N=3, M=4인 경우 학생들의 능력치가 1반=[12, 16, 67, 43],  2반=[7, 17, 68, 48], 3반=[14, 15, 77, 54]로 주어질 때, 각 학급으로부터 능력치 16, 17, 15를 가진 학생을 각각 선택하면, 최댓값과 최솟값의 차이가 17-15=2로 최소가 된다. 

대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 출력하는 프로그램을 작성하시오.

 

입력

---

입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학급 학생들의 능력치를 나타내는 M개의 양의 정수가 하나의 빈칸을 사이에 두고 주어진다. 능력치는 0이상 10⁹이하이다.

 

출력

---

대표로 선발된 모든 학생들 능력치의 최댓값과 최솟값 차이가 최소가 되는 경우의 값을 하나의 정수로 출력한다.

 

문제 풀이

---

투포인터 문제.

모든 학생을 배열에 입력받은 후 정렬하여, start와 end를 0으로 초기화한다. end를 늘려가면서 start와 end 사이에 모든 학급이 포함될 수 있도록 범위를 찾는다. 만약 모든 학급이 포함되었다면 end를 마지막으로 하면서 최소의 길이를 갖도록 start를 늘려가며 찾는다. 모든 학급이 포함된 범위 내에서는 그 인덱스를 갖는 학생들이 대표가 된다. end 인덱스를 갖는 학생의 능력치 - start 인덱스를 갖는 학생의 능력치가 우리가 구하는 answer가 되고, end를 끝까지 증가시켜가며 answer의 최솟값을 찾으면 된다.

알고리즘 자체는 어렵지 않지만 유형을 떠올리기 어려운 문제.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <utility>
#include <map>
using namespace std;

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

	int N, M;
	int start = 0;
	int end = 0;
	cin >> N >> M;
	pair<int, int>* arr = new pair<int, int>[N * M];
	map<int, int> m;
	map<int, int>::iterator it;
	int answer = 1000000000;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> arr[M * i + j].first;
			arr[M * i + j].second = i+1;
		}
	}
	sort(arr, arr + N * M);
	while (end < N * M)
	{
		it = m.find(arr[end].second);
		if (it == m.end())
		{
			m.insert({ arr[end].second, 1 });
		}
		else
		{
			it->second++;
		}
		while (m.size() == N)
		{
			answer = min(answer, arr[end].first - arr[start].first);
			it = m.find(arr[start].second);
			if (it->second == 1)
			{
				m.erase(it);
			}
			else
			{
				it->second--;
			}
			start++;
		}
		end++;
	}
	cout << answer << "\n";
	return 0;
}