[c++] 백준 11286번 절댓값 힙

김진웅·2023년 12월 28일

11286 11286번 C 백준 우선순위 큐 절댓값 힙

baekjoon-study

목록 보기

43/59

링크
https://www.acmicpc.net/problem/11286

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

배열에 정수 x (x ≠ 0)를 넣는다.
배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 $-2^{31}$ 보다 크고, $2^{31}$ 보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1

예제 출력 1

아이디어 스케치

우선순위 큐 자료구조를 이용하여 해결하는 문제이다. 하지만 단순히 오름차순 or 내림차순으로 정렬된 우선순위 큐가 아닌 문제에서 제시하는 조건에 맞게 우선순위를 설정하여 문제를 해결해야 한다.

문제에서 제시한 조건은 먼저 절댓값을 기준으로 오름차순 정렬을 수행한 후, 절댓값이 같은 경우에는 값을 기준으로 오름차순 정렬을 수행한다. 즉, 절댓값이 작을수록 우선순위가 높고, 절댓값이 같은 경우에는 더 작은 값이 더 높은 우선순위를 갖는다.

C++에서는 priority_queue에 들어가는 cmp 구조체의 operator()연산자를 위 문제에서 제시한 조건에 맞게 오버로딩을 하면 된다.

struct cmp {
	// operator() 오버로딩
	bool operator()(int n1, int n2) {
		if (abs(n1) > abs(n2))	// 큐에 새로 넣을 인자(n2)의 절대값이 큐에 있는 비교 인자(n1)보다 작을 경우
			return true;		// n2의 우선순위를 올림
		else if (abs(n1) == abs(n2)) {	// 두 수의 절대값이 같은 경우
			if (n1 > n2)		// n2가 더 작은 경우에
				return true;	// n2의 우선순위를 올림
			else
				return false;
		}
		return false;
	}
};

위 코드는 cmp 구조체를 새로 생성하여 operator() 연산자를 오버로딩 하는 코드이다.

n1 인자가 큐에 이미 존재하는 인자(비교 대상), n2 인자가 큐에 새로 넣은 인자이다. n2의 절댓값이 n1의 절댓값보다 작은 경우에 return true을 해준다.(n2의 우선순위를 올림)

n1 인자와 n2인자의 절댓값이 같은 경우에는 절댓값이 아닌 원래의 값을 비교하여 n2가 더 작은 경우에 n2의 우선순위를 올린다.

전체코드

#include <iostream>
#include <queue>
using namespace std;


struct cmp {
	// operator() 오버로딩
	bool operator()(int n1, int n2) {
		if (abs(n1) > abs(n2))	// 큐에 새로 넣을 인자(n2)의 절대값이 큐에 있는 비교 인자(n1)보다 작을 경우
			return true;		// n2의 우선순위를 올림
		else if (abs(n1) == abs(n2)) {	// 두 수의 절대값이 같은 경우
			if (n1 > n2)		// n2가 더 작은 경우에
				return true;	// n2의 우선순위를 올림
			else
				return false;
		}
		return false;
	}
};

int main() {
	// 시간초과 방지
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	priority_queue<int, vector<int>, cmp> q;	// 우선순위 큐 선언(int자료형, cmp 비교함수 기준으로 정렬)

	int N;		// 연산 횟수
	int input;	// 입력 값

	cin >> N;	// 연산 횟수를 입력 받음

	while (N--) {
		cin >> input;
		if (input == 0) {	// 입력 값이 0이면
			if (q.empty())	// 큐가 비었다면
				cout << 0 << '\n';	// 0 출력
			else {
				cout << q.top() << '\n';	// 큐의 최상단 노드를 출력하고
				q.pop();					// 꺼냄
			}
		}
		else
			q.push(input);		// 큐에 입력 값을 넣음
	}

	return 0;
}