[백준 5926] Cow Lineup

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

5926번: Cow Lineup

#include <cstdio>
#include <unordered_map>
#include <algorithm>
using namespace std;
int N;

struct _st
{
	int x;
	int id;
}Cow[50000 + 2];

bool COMP(_st &a, _st &b)
{
	return a.x < b.x;	// cost를 기준으로 오름차순 정렬
}


unordered_map<int, int> ID;	// 원래 아이디, 변경 아이디 
int chk[50000 + 2];

void input()
{
	scanf("%d", &N);
	int num = 0;
	for (int i = 0; i < N; i++) {
		int pos = 0; int type = 0;
		scanf("%d %d", &pos, &type);
		Cow[i].x = pos;
		if (ID.find(type) == ID.end()) {	// 입력받은 type이 map에 없다면
			ID.insert({ type, num });		// type을 num으로 맵핑
			Cow[i].id = num;				// Cow[i].id에 입력받은 type이 아닌, 변환한 num을 대입 
			num++;
		}
		else Cow[i].id = ID[type];			// 입력받은 type이 map에 있다면 맵핑한 num 대입
	}
	sort(Cow, Cow + N, COMP);		// 최소비용을 계산해야 하므로 cost를 기준으로 오름차순 정렬한다. 
	// printf("%d", ID.size());
}

int get_cost()
{
	int min = 0x7fffffff;
	int total_cnt = ID.size();	// 전체 품종 개수
	int cnt = 0; // 현재 품종 개수
	int e = 0;	 // 현재 끝점 

	for (int i = 0; i < N; i++) {
		// 각 시작점에서 모든 소의 품종을 포함하는 끝 점을 계산한다. 
		while (1) {
			if (e == N || cnt == total_cnt) break;
			chk[Cow[e].id] += 1;
			if (chk[Cow[e].id] == 1) cnt++;
			e++;
		}
		if (e == N && cnt < total_cnt) break; // 전체 탐색했는데 현재 품종개수가 전체품종 개수보다 적으면 더이상 탐색할 필요 없음 
		
		int tmp = Cow[e - 1].x - Cow[i].x;
		//printf("%d ", tmp);
		min = (tmp < min) ? tmp : min;
		
		chk[Cow[i].id] -= 1;
		if (chk[Cow[i].id] == 0) cnt--;
	}
	return min;
}



int main()
{
	input();
	int ans = get_cost();
	printf("%d\n", ans);
	return 0;
}

트리키 트리키... 어렵다 슬라이딩 윈도우.. 

 

 

이 문제에서 주의해야 할 점은 두 가지였다. 

1. 값이 1억인 아이디가 들어올 수 있다. => 이것을 룩업테이블로 확인해 줄 것인가 ? 

2. 슬라이딩 윈도우의 사이즈가 계속 변한다. => 기존에 배웠던 유형은 "동일한 크기의 윈도우가 이동하는 방식"이었는데, 이 문제의 경우 어떻게 슬라이딩 윈도우를 움직일 것인가 ? 

 

 

// input( ) 함수

첫 번째 주의해야할 점에 대한 해결방안은 "unordered_map"을 사용하는 것이다. 어차피 소는 50,000마리까지 입력되므로, map의 사이즈는 최대 50,000이다. 만약 값이 1억인 id가 입력된다면, 그것을 적절한 다른 숫자로 바꾸어 mapping 해준다. 이렇게 하면 사이즈 1억짜리 룩업테이블을 사용하지 않아도, 해당 id가 있는지 없는지 확인하는 사이즈 50,000짜리 체크 배열을 운영할 수 있다. 

 

또한 모든 종류의 소들을 한 마리씩 포함하게 하면서는 최소의 비용을 구해야 하므로, 비용을 기준으로 오름차순 정렬해주었다.

 

 

// get_cost( ) 함수

최소 비용을 찾기 위해 min을 0x7fffffff로 초기화해주고, 전체 품종의 개수는 현재 ID라는 map에 저장된 원소의 개수이다. 

두 번째 주의해야할 점에 대한 해결방안은, 모든 시작점에 대한 슬라이딩 윈도우의 최소 크기를 찾는 것이다.  

 

(1) 이를 위해 for루프를 돌리면서 각 시작점을 탐색해주었다.

(2) while 루프를 돌리면서 시작점 i에서 품종개수 cnt가 전체 품종개수 total_cnt가 될때 까지 e를 증가시켜준다. 만약 끝점 e가 마지막 인덱스보다 큰 값에 도달하거나, 현재 품종개수가 전체 품종개수와 같아질 경우 루프를 탈출한다. 

또한 새로 추가된 인덱스 e 소의 id가 0에서 1로 바뀌었다면, 끝점이 이동하면서 새로운 품종의 소가 추가된 것이므로 현재 품종개수 cnt를 증가시킨다. 

(3) while루프를 빠져나온 후, 만약 끝 인덱스 e가 마지막 인덱스에 도달하였는데 현재 품종의 개수가 전체 품종의 개수보다 적은 경우, 더이상 탐색할 필요가 없다. 추가할 소가 없기 때문이다. 그러므로 for 루프를 중단해준다. 

(4) while 루프를 빠져나오면서 cnt == total_cnt 이지만, 끝 인덱스는 해당 조건을 만족한 e보다  1이 더 증가된 상태이기 때문에 현재 비용(tmp)를 구할때는 인덱스 e - 1부터 i까지를 구해준다. 

(5) 다음 시작점에서부터의 탐색을 위해 현재 시작점 소의 id를 chk 배열에서 삭제해준다. 만약 삭제한 인덱스 i 소의 id가 1에서 0으로 바뀌었다면, 시작점 소를 제거하면서 품종이 한 개 사라진 것이므로 현재 품종개수 cnt를 감소시킨다.