문제

문제 링크

문제 접근

  • 이 문제를 풀다가 disjoint set이 떠올랐다면, union-find 알고리즘이 떠올랐다면 당신은 대단한 사람이다!
  • 4번이 비어있고 도킹되는 위치를 4라고 하면 4번은 도킹되고 4번을 도킹하려 할때의 결과물은 3번을 도킹하려할 때와 같이 1~3번 사이를 봐야한다.
  • 즉 4번이 도킹되면서 4-1인 3과 union되는 것으로 볼 수 있다!

초기 union-find 코드

#include <cstdio>

int P[500001], par[500001], g, p;

int find(int i){
    if(par[i] == -1)return i;
    return find(par[i]);
}
int main(){
    scanf("%d %d", &g, &p);
    for(int i = 0; i < g + 1; i++)par[i] = -1;
    for(int i = 0; i < p; i++)scanf("%d", &P[i]);
    for(int i = 0; i < p; i++){
        int x = P[i];
        int px = find(x);
        if(!px){
            printf("%d", i);
            return 0;
        }
        int py = find(px - 1);
        par[px] = py;
    }
}
  • 오히려 느려졌다… 15%에서 시간초과가 뜨게 된다..!

개선된 find 코드

int find(int i){
    if(par[i] == -1)return i;
    return par[i] == find(par[i]);
}
  • find를 하면서 중간다리도 다 업데이트 시켜줌으로써 시간이 엄청 빨라지게 된다.

최종 코드

int find(int i){
    if(par[i] == i)return i;
    return par[i] = find(par[i]);
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> g >> p;
    for(int i = 0; i < g + 1; i++)par[i] = i;
    for(int i = 0; i < p; i++){
        cin >> x;
        int px = find(x);
        if(!px)break;
        //Union
        par[px] = find(px - 1);
        ans ++;
    }
    cout << ans;
}

느낀점

  • 이전에 union find 알고리즘을 사용할 때도 중간에 업데이트 시켜주지는 않았는데 오히려 저렇게 하는 게 시간이 훨씬 덜 걸리는 걸 보고 조금은 충격을 먹었다.
  • 나중에 union-find를 사용할 때도 같은 방식으로 중간중간 업데이트 할 수 있게 해야겠다.