FENCE 문제를 유니온 파인드를 이용해서 푸는 방법 중 질문이 있습니다 ^^ infoefficiency https://algospot.com/judge/problem/read/FENCE 판자들을 높이 순으로 오름차순 한 뒤 추가하면서 연결된 판자들의 집합을 통해 구하는 것은 감이 오는데 시간 복잡도가 nlogn이 되도록 하려니까 정확한 해법이 떠오르지가 않습니다.ㅠ 혹시나 가능하시다면 조금의 힌트좀 부탁드립니다 ㅠ 감사합니다 ^^ 9년 전
1개의 댓글이 있습니다. Being 정렬에 O(N \lg N)이고, 정렬 후에는 뭐 어떤 방법을 구체적으로 생각하시는지는 모르겠으나, 서로소 집합 자료 구조를 잘 구현했다면 각 쿼리당 사실상 상수 시간인데 무엇을 고민하시는지요? 9년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
infoefficiency
https://algospot.com/judge/problem/read/FENCE
판자들을 높이 순으로 오름차순 한 뒤
추가하면서 연결된 판자들의 집합을 통해 구하는 것은 감이 오는데 시간 복잡도가 nlogn이 되도록 하려니까
정확한 해법이 떠오르지가 않습니다.ㅠ
혹시나 가능하시다면 조금의 힌트좀 부탁드립니다 ㅠ
감사합니다 ^^
9년 전