[백준/BOJ] 백준 5926번 : Cow Lineup

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

5926번: Cow Lineup

 

x좌표 순으로 소의 정보를 정렬하고, 투 포인터를 이용해 모든 품종을 포함하는 최소 범위의 x좌표 구간을 구해서 문제를 해결했다.

 

코드

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

int n;
vector<pair<int, int>> cows;
set<int> cow_type;
int cow_type_cnt;

int main() {

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int x, type_id;
		cin >> x >> type_id;

		cow_type.insert(type_id);

		cows.push_back(make_pair(x, type_id));
	}

	cow_type_cnt = cow_type.size();

	//x좌표 순으로 정렬
	sort(cows.begin(), cows.end());

	int left = 0;
	int right = -1;
	int result = 1000000005;
	map<int, int> cow_check;

	while (1) {

		//현재 범위 안에서 모든 품종이 포함될때
		if (cow_check.size() == cow_type_cnt) {

			result = min(result, cows[right].first - cows[left].first);

			cow_check[cows[left].second]--;

			if (cow_check[cows[left].second] == 0) {
				cow_check.erase(cows[left].second);
			}

			left++;

			continue;
		}

		//다 확인 했을때
		if (left >= n || right + 1 >= n) {
			break;
		}

		//현재 범위 안에서 모든 품종이 포함되지 않을때
		//소 추가
		right++;
		if (cow_check.count(cows[right].second) == 0) {
			cow_check.insert(make_pair(cows[right].second, 1));
		}
		else {
			cow_check[cows[right].second]++;
		}

	}

	cout << result;

	return 0;
}