[백준 14427] 수열과 쿼리 15(C++: Updatable PQ)

A. 문제설명

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

14427번: 수열과 쿼리 15

문제 설명은 다음과 같다.

길이가 N인 수열 A1, A2, ..., AN이 주어진다.
이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109)
2 : 수열에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러 개인 경우에는 인덱스가 작은 것을 출력한다.

 

한마디로 중간에 내부 값을 업데이트하고 우선순위를 유지하는 우선순위 큐를 구현하라는 것이다.

 

B. 접근법

Updatable PQ(with update & downdate)

 

인터넷에 세그먼트 트리를 활용한 풀이들이 여럿 올라와있지만, 나는 변경가능한 우선순위 큐를 직접구현하여 이 문제를 해결해보고자 한다.

 

일반적인 우선순위 큐(힙)를 생각해보자. MinHeap을 생각하자면, 가장 작은 값이 root에 들어가고, 그 다음 작은 값들이 자식들에 들어가고, 그 다다음 작은 값들이 그 자식들의 자식으로 들어가고... 이 구조가 반복된다.

 

먼저 힙에 원소를 push하는 과정을 생각해보자면 다음과 같다.

1. 힙의 마지막에 새로 push하는 원소를 삽입하고

2. 해당 원소를 부모와 비교해가며 올릴 수 있는 만큼 올린다.

3. 마지막으로 heapSize를 증가시킨다.

void update(int current){
	while (current>0 && heapComp(heap[current], heap[(current-1)/2])) {
		heapSwap((current-1)/2, current);
		current = (current-1)/2;
	}
}

여기서, 2번의 원소를 올리는 과정은 위 코드 update()와 같다.

 

두 번째로, 힙에서 top을 빼는 pop을 생각해보자.

1. 먼저 반환할 top을 임시 변수에 저장한다.

2. top과 heapSize인 마지막 인덱스에 있는 원소를 swap한다.

3. top으로 올라간 원소는 우선순위가 가장 높은 놈이 아닐 수 있으므로 해당 원소를 자식들과 비교해가며 내릴 수 있는 만큼 내린다.

4. 마지막으로 heapSize를 감소시킨다.

void downdate(int current){
	while (current*2+1 < heapSize) {
		int child;
		if (current*2+2 == heapSize) child = current*2+1;
		else child = heapComp(heap[current*2+1], heap[current*2+2]) ? current*2+1 : current*2+2;

		if (heapComp(heap[current], heap[child])) break;
		heapSwap(current, child);
		current = child;
	}
}

여기서 3번의 원소를 내리는 과정은 위 코드 downdate()와 같다.

 

자... 여태까지 이렇게 장황하게 update와 downdate에 대해 설명한 이유는 힙의 원소를 변경시키고 우선순위 상태를 유지시키기 위해 update-downdate만 해주면 되기 때문이다.

여기서 추가로 필요한 것은, 내가 바꾸고 싶은 원소의 인덱스이다. 해당 값은 힙의 크기만큼 배열로 잡아 원소의 ID에서 바로 원소의 힙 인덱스를 가리킬 수 있는 자료구조를 저장한다.(heapSwap시 이 인덱스도 매번 업데이트 해주어야 한다.)

void heapUpdate(int idx, int val) {
	heap[index[idx]].first = val;
	update(index[idx]);
	downdate(index[idx]);
}

따라서, heapUpdate()의 구현은 위와 같다. 원하는 위치에 값을 삽입하고, 해당 인덱스에서 update-downdate 해준다.

 

C. 내 코드

전체 코드는 아래와 같다.