[BOJ] 백준 5926 Cow Lineup

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

 Input 

6

25 7

26 1

15 1

22 3

20 1

30 1

 

 Output 

4

① Hash를 통해 중복되지 않은 소(cow)들의 종류 수를 확인합니다.

    ex) 1 3 7 → 총 3마리

② 소들에게 새로운 ID를 부여합니다. (발견된 종류 순서로 부여)

    1 → 1 / 3 → 2 / 7 → 3

③ (새로운 ID까지 부여된) 소들은 x 좌표 기준으로 오름차순 정렬합니다. (merge sort)

④ end 좌표를 확장해가며 소들의 종류가 빠짐없이 포함되는 지점을 찾습니다.

⑤ end 지점을 찾은 후 start 지점을 조정하여 최적(최소) 범위를 조정합니다.

첫번째 s = 1일 때, 모든 종류의 소를 포함하려면 e = 5

하지만 s = 2, s = 3 위치에서도 모든 종류의 소들을 포함할 수 있습니다.

 

▶ [해시] Hash란?

[해시] Hash란?

---

#include <stdio.h>
 
const int MAX_N = 5e4;
const int INF = 2e9;
inline int min(int A, int B) { if (A < B) return A; return B; }
int N, ans = INF, typeCnt;
int check[MAX_N + 10];
struct COW {
    int x, ID;
}cows[MAX_N + 10], trr[MAX_N + 10];
 
struct Node {
    int ID, newID;
    Node* next;
 
    Node* alloc(int ID, int newID, Node* np) {
        this->ID = ID;
        this->newID = newID;
        next = np;
        return this;
    }
}buf[MAX_N + 10], *htab[MAX_N];
int bcnt;
 
bool comp(COW A, COW B) {
    return A.x < B.x;
}
 
void mergeSort(int start, int end) {
    if (start >= end)
        return;
 
    int mid = (start + end) / 2;
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
 
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (comp(cows[i], cows[j]))
            trr[k++] = cows[i++];
        else
            trr[k++] = cows[j++];
    }
    while (i <= mid) trr[k++] = cows[i++];
    while (j <= end) trr[k++] = cows[j++];
 
    for (i = start; i <= end; ++i) {
        cows[i] = trr[i];
    }
}
 
Node* probing(int key, int ID) {
    Node* p = htab[key];
    for (; p; p = p->next) {
        if (p->ID == ID)
            return p;
    }
    return NULL;
}
 
int insertHashData(int ID) {
    int key = ID % MAX_N;
    Node* p = probing(key, ID);
    // 기존에 없는 정보인 경우 새롭게 등록
    if (!p) {
        htab[key] = buf[bcnt++].alloc(ID, typeCnt, htab[key]);
        return typeCnt++;
    }
    // 기존 등록된 경우
    return p->newID;
}
 
void input() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d %d", &cows[i].x, &cows[i].ID);
        // Hash Table에 등록 후 새로운 ID 부여
        // MAX_N(5만) 이하의 ID로 새롭게 부여
        cows[i].ID = insertHashData(cows[i].ID);
    };
}
 
void solve() {
    mergeSort(0, N - 1);
    int cnt = 0;
    for (int s = 0, e = 0; e < N; e++) {
        // 범위 안에 중복되지 않은 종류 수 확인
        if (!check[cows[e].ID]) cnt++;
        check[cows[e].ID]++;
        // s의 범위를 조정하며 범위 최소화
        while (check[cows[s].ID] >= 2) {
            check[cows[s].ID]--;
            s++;
        }
        // 범위안에 종류 수와 Hash Table상에 등록된 종류 수 비교
        if (cnt < typeCnt) continue;
        // 최적의 해
        ans = min(ans, cows[e].x - cows[s].x);
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    solve();
    printf("%d\n", ans);
}