[우선순위큐] 백준 14427번 : 수열과 쿼리 15 - C/C++

www.acmicpc.net/problem/14427

14427번: 수열과 쿼리 15

 

1. 문제

길이가 N인 수열이 주어진다.

1을 입력받으면, 주어진 수열에서 가장 작은 값의 인덱스를 출력한다.

2를 입력받으면, i번째 수열의 값을 v로 바꾼다.

 

2. 해결

1) 가장 작은 값만 필요하기 때문에 우선순위 큐를 이용하였다.

 

2) 수열의 각 정보는 Node 구조체로 구성하였다. 

- num : 수열의 값

- heapIndex : 2를 입력받으면, 해당 힙의 위치 기준으로 자기 자리를 찾기 위해 힙의 인덱스 값도 저장

 

3) 힙은 node의 인덱스 값을 저장하여 우선순위 큐를 구성하도록 하였다.

 

4) 수열이 주어지면 차례대로 node 배열에 추가하고, nodeIndex를 heap에 push 한다.

(기존 우선순위큐 구현과 다른 점은, heap에서 위치가 바뀔 때마다 heap의 index를 저장해준다.)

 

5) 1을 입력받으면 heap의 top (heap[0]) 을 출력

 

6) 2를 입력받으면, i번째 node의 num을 바꾸고, 그 node의 heapIndex 기준으로 update, downdate를 해준다.

(heap은 항상 부모가 자식보다 우선순위가 높다는 것이 자명하기 때문에, update 또는 downdate 둘 중에 하나만 실행되며 자기 자리를 찾는다.)

3. 코드

#include <stdio.h>

struct Node {
	int heapIndex;
	int num;
} node[100001];
int nodeIndex = 1;

int heap[100001];
int heapSize = 0;

int compare(int a, int b) {
	return (node[a].num < node[b].num) || (node[a].num == node[b].num && a < b);
}

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

		if (compare(heap[current], heap[child])) break;

		int temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;

		node[heap[current]].heapIndex = current;
		node[heap[child]].heapIndex = child;

		current = child;
	}
}

void update(int current) {
	while (current > 0 && compare(heap[current], heap[(current - 1) / 2])) {
		int root = (current - 1) / 2;
		int temp = heap[root];
		heap[root] = heap[current];
		heap[current] = temp;

		node[heap[current]].heapIndex = current;
		node[heap[root]].heapIndex = root;

		current = root;
	}
}

void heapPush(int index) {
	heap[heapSize] = index;
	node[index].heapIndex = heapSize;
	update(heapSize);
	heapSize++;
}

int main() {
	int N;
	scanf("%d", &N);
	
	for (int i = 0; i < N; ++i) {
		scanf("%d", &node[nodeIndex].num);

		heapPush(nodeIndex);

		nodeIndex++;
	}

	int M;
	scanf("%d", &M);

	for (int i = 0; i < M; ++i) {
		int query;
		scanf("%d", &query);

		if (query == 1) {
			int fromIndex, toValue;
			scanf("%d %d", &fromIndex, &toValue);

			node[fromIndex].num = toValue;
			update(node[fromIndex].heapIndex);
			downdate(node[fromIndex].heapIndex);
		}
		else if (query == 2) {
			printf("%d\n", heap[0]);
		}
	}
}

 

GitHub

geonhee7721/PS-Backjoon

 

 

※ 우선순위큐 관련 이전 문제

2021.03.07 - [알고리즘/백준] - [우선순위큐] 백준 1655번 : 가운데를 말해요 - C/C++