[문제풀이] 5926번: Cow Lineup

[문제풀이] 5926번: Cow Lineup

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

문제유형

해쉬 테이블 (Chaining)

Solution

시간 오래 걸리고 어려웠던 문제.

암소들의 위치와 아이디가 각각 주어지는데, 연속적인 최소범위 내에 모든 아이디가 들어가야하는 문제.

아이디가 10억번까지 주어지고 총 데이터는 50000개 정도.

아이디 숫자가 너무 커서 500233 으로 MOD HASH TABLE을 구현해주었음.

충돌이 일어나는 부분은 CHAINING을 사용함.

모든 아이디가 범위 안에 포함되도록 범위의 start와 end를 잡아야 했는데 중복 아이디를 체크하기 위해 NODE마다 check 정보를 저장하고 동일 아이디의 개수를 저장함.

주의할 점은 start를 먼저 잡냐 end를 먼저 잡냐에 따라 답이 미묘하게 달라서 각각 계산한 뒤 최소 범위를 다시 구해야 했다는 점.

#include <cstdio>
 
int N;
struct COW
{
    long long ID;
    long long pos;
    COW()
    {
        ID = 0; pos = 0;
    }
};
COW cows[50010];
 
#define MOD 500233
struct NODE
{
    long long id;
    int check;
    NODE* next;
    NODE()
    {
        id = -1;
        check = 0;
        next = NULL;
    }
};
NODE hash_table[MOD + 10];
int count;
 
int calcHash(long long id)
{
    return id % MOD;
}
 
int inputHash(int hash, long long id)        //chaining
{
    NODE* head = &hash_table[hash];
 
    if (head->id == -1)
    {
        head->id = id;
        head->next = NULL;
        return 1;
    }
    else if (head->id == id) return 0;
    else if (head->id)
    {
        while (head->next != NULL)
        {
            if (head->id == id) return 0;
            head = head->next;
        }
 
        NODE* newnode = new NODE();
        newnode->id = id;
        head->next = newnode;
        return 1;        
    }
    return 0;
}
 
void setupHash(int hash, long long id)
{
    NODE* head = &hash_table[hash];
 
    if (head->id == id) head->check++;
    else if (head->id != id)
    {
        while (head->next != NULL)
        {
            if (head->id == id)
            {
                head->check++;
                return;
            }
            head = head->next;
        }
    }
    return;
}
 
void initHash(int hash, long long id)
{
    NODE* head = &hash_table[hash];
 
    if (head->id == id) head->check = 0;
    else if (head->id != id)
    {
        while (head->next != NULL)
        {
            if (head->id == id)
            {
                head->check = 0;
                return;
            }
            head = head->next;
        }
    }
    return;
}
 
void inputData()
{
    scanf("%d", &N);
    for (register int i = 0; i < N; i++)
    {
        scanf("%lld %lld", &cows[i].pos, &cows[i].ID);
        long long id = cows[i].ID;
        count += inputHash(calcHash(id), id);
    }
}
 
void quickSort(int s, int e)
{
    COW tmp;
    int pivot, left, target = s;
 
    pivot = e;
 
    if (s >= e) return;
 
    for (left = s; left < e; left++)
    {
        if (cows[left].pos <= cows[pivot].pos)
        {
            if (target != left)
            {
                tmp = cows[left];
                cows[left] = cows[target];
                cows[target] = tmp;
            }
            target++;
        }
    }
 
    if (target < pivot)
    {
        tmp = cows[pivot];
        cows[pivot] = cows[target];
        cows[target] = tmp;
    }
 
    quickSort(s, target-1);
    quickSort(target+1, e);
 
}
 
int searchHash(int hash, long long id, NODE** ret)
{
    NODE* head = &hash_table[hash];
    
    if (head->id == id)
    {
        *ret = head;
        return 1;
    }
    else if (head->id != id && head->next)
    {
 
        while (head->next != NULL)
        {
            if (head->id == id)
            {
                *ret = head;
                return 1;
            }
            head = head->next;
        }
    }
    return 0;
}
 
long long solve()
{
    NODE* ret;
    long long sol = 0;
    long long int start, end;
    int i;
    int flag = 0;
 
    for (i = 0; i < N; i++)
    {
        long long id = cows[i].ID;
        setupHash(calcHash(id), id);
    }
 
    //search1
    for (i = 0; i < N; i++)
    {
        if (flag) break;
        long long id = cows[i].ID;
        
        if (searchHash(calcHash(id), id, &ret))
        {
            if (ret->check == 1)
            {            
                
                start = cows[i].pos;
                flag = 1;
            }
            else
            {
                ret->check--;
            }
        }
    }
 
    //search2
    flag = 0;
    for (i = N - 1; i >= 0; i--)
    {
        if (flag) break;
        long long id = cows[i].ID;
        if (searchHash(calcHash(id), id, &ret))
        {
            if (ret->check == 1)
            {
                end = cows[i].pos;
                flag = 1;
            }
            else ret->check--;
        }
    }
 
    sol = end - start;
 
    //////////////////////////////
    for (i = 0; i < N; i++)
    {
        long long id = cows[i].ID;
        initHash(calcHash(id), id);
    }
 
    for (i = 0; i < N; i++)
    {
        long long id = cows[i].ID;
        setupHash(calcHash(id), id);
    }
 
    //search2
    flag = 0;
    for (i = N - 1; i >= 0; i--)
    {
        if (flag) break;
        long long id = cows[i].ID;
        if (searchHash(calcHash(id), id, &ret))
        {
            if (ret->check == 1)
            {
                end = cows[i].pos;
                flag = 1;
            }
            else ret->check--;
        }
    }
 
    //search1
    flag = 0;
    for (i = 0; i < N; i++)
    {
        if (flag) break;
        long long id = cows[i].ID;
 
        if (searchHash(calcHash(id), id, &ret))
        {
            if (ret->check == 1)
            {
 
                start = cows[i].pos;
                flag = 1;
            }
            else
            {
                ret->check--;
            }
        }
    }
 
    if (sol > end - start) sol = end - start;
 
    return sol;
}
 
int main()
{
    inputData();
    quickSort(0, N-1);
    printf("%lld", solve());
 
    return 0;
}