백준 7469번 K번째 수

알고리즘/BOJ

꾸준함. 2025. 1. 18. 21:55

좌표 압축과 퍼시스턴트 세그먼트 트리를 이용하는 문제였습니다.

퍼시스턴트 세그먼트 트리 관련해서는 justicehui님 블로그를 참고하시면 될 것 같습니다.

Persistent Segment Tree

서론 어떤 자료구조가 “persistent하다”라는 것은, 상태의 변화가 생기더라도 과거 상태를 모두 보존하고 있다는 것을 의미합니다. Persistent Segment Tree(PST)는 세그먼트 트리의 갱신 과정을 모두 저

justicehui.github.io

알고리즘은 다음과 같습니다.

1. 배열 a의 값들이 [-10^9, 10^9] 범위를 갖기 때문에 세그먼트 트리의 인덱스로 직접 쓰기에는 범위가 너무 광범위합니다.

1.1 이에 따라 배열 값들을 정렬 후 중복 제거하여 좌표 압축을 진행해야 합니다.

1.2 compArr[i]는 a[i]의 압축된 값 즉, 1부터 시작하는 인덱스 값을 저장합니다.

2. 퍼시스턴트 세그먼트 트리를 구성합니다.

2.1 root[i]는 `배열의 앞에서부터 i 번째 원소까지 반영된 세그먼트 트리`의 루트 노드입니다.

2.2 root[0]은 아무 원소도 반영되지 않은 빈 세그먼트 트리로 구성합니다.

2.3 이후 i 번째 원소를 삽입할 때마다 이전 버전 root[i - 1]을 복사하면서 새로운 좌표(압축값 인덱스)만 +1 해줍니다.

2.4 퍼시스턴트 세그먼트 트리이기 때문에 새 노드는 필요한 부문만 복사하며 전체 트리를 중복해서 만들지 않습니다.

3. 쿼리 Q(i, j, k)를 계산하고 출력합니다.

3.1 root[j]와 root[i - 1] 두 버전을 비교하면 구간 [i, j]에 들어 있는 원소들의 빈도 정보를 얻을 수 있습니다.

3.2 세그먼트 트리를 내려가면서 `왼쪽 자식에 몇 개가 있는가`를 확인해 k를 조정해 나가는 방식으로 k 번째 원소의 압축값을 찾은 뒤 해당 압축값을 원래 값으로 되돌려 출력합니다.

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~