[백준/BOJ] 백준 2461번 : 대표 선수

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

2461번: 대표 선수

vector<pair<int, int>> people에 (학생의 능력치, 속한 반)를 저장 후 정렬 뒤 투 포인터를 이용하여 문제를 해결했다. map<int, int> check에 [반] = 구간에서 반에 속한 학생의 수를 저장하여 check.size()가 n과 같은지를 확인해서 범위 안에 각 반의 학생이 한명이상 있는지를 체크했다.

 

코드

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

int n, m;
vector<pair<int, int>> people; //(학생의 능력치, 속한 반)
map<int, int> check; //[반] = 구간에서 반에 속한 학생의 수
map<int, int>::iterator it;

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

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int input;
			cin >> input;

			people.push_back(make_pair(input, i));
		}
	}

	sort(people.begin(), people.end());

	int left = 0;
	int right = 0;
	int result = 987654321;

	while (1)
	{
		//범위 안에 각 반의 학생이 한명이상 있을때
		if (check.size() == n)
		{
			//최대랑 최소가 같은 반이 아닐때
			if (people[right - 1].second != people[left].second)
				result = min(result, people[right - 1].first - people[left].first);

			//left 왼쪽으로 옮기기
			check[people[left].second]--;

			if (check[people[left].second] == 0)
			{
				check.erase(people[left].second);
			}

			left++;
		}

		else
		{
			if (right >= people.size())
				break;

			if (check.count(people[right].second) == 0)
			{
				check.insert(make_pair(people[right].second, 1));
			}

			else
			{
				check[people[right].second]++;
			}

			right++;
		}
	}

	cout << result;

	return 0;
}