FENCE 문제를 유니온 파인드를 이용해서 푸는 방법 중 질문이 있습니다 ^^

  • infoefficiency
    infoefficiency

    https://algospot.com/judge/problem/read/FENCE

    판자들을 높이 순으로 오름차순 한 뒤
    추가하면서 연결된 판자들의 집합을 통해 구하는 것은 감이 오는데 시간 복잡도가 nlogn이 되도록 하려니까
    정확한 해법이 떠오르지가 않습니다.ㅠ

    혹시나 가능하시다면 조금의 힌트좀 부탁드립니다 ㅠ
    감사합니다 ^^


    5년 전
1개의 댓글이 있습니다.
  • Being
    Being

    정렬에 O(N \lg N)이고, 정렬 후에는 뭐 어떤 방법을 구체적으로 생각하시는지는 모르겠으나, 서로소 집합 자료 구조를 잘 구현했다면 각 쿼리당 사실상 상수 시간인데 무엇을 고민하시는지요?


    5년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.