백준 11286번 절댓값 힙(c++)

11286번: 절댓값 힙

문제 분석

문제는 입력받는 숫자 중 절댓값이 가장 작은 숫자를, 만약 절댓값이 같다면 수가 가장 작은 수를 기준으로 정렬시키려 한다. 그리고 0을 입력받았을 때, 위의 조건에서 가장 앞에 정렬된 숫자를 출력하고 삭제한다. 결국 배열을 정렬시키는 정렬방식이 가장 핵심이라고 할 수 있다.

---

문제 풀이

 첫 접근은 swap함수를 이용한 정렬이었다. 입력받은 숫자를 하나의 배열에 집어넣고, 집어넣은 숫자와 옆숫자와 서로의 절댓값을 비교하도록 했다. 위 방식은 swap함수를 지속적으로 사용하기에, 시간 초과를 유발하게 되었다.(잘못된 방식)

 결국 숫자를 넣었을 경우, 자동으로 정렬이 되도록 하는 방식을 사용해야한다. 가장 적합한 알고리즘은

'우선순위 큐'

이다. 중요한 점은 우선순위 큐의 정렬방식을 직접 설정해야한다. 

ex) priority_queue<int, vector<int>, abc> que;
-> 이는 int형 변수들을 abc의 정렬방식에 따라 정렬하는 que라는 이름의 우선순위를 선언한다.

위 abc는 struct형태로 선언하고, 정렬방식을 설정하면 된다.

아래 코드를 보면서 더욱 공부하면 좋다고 생각한다.

---

c++ 풀이

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct avs { 
// 자체 정렬(절댓값 작은 숫자 앞으로, 같은 절댓값일 때 음수값을 앞으로)
	bool operator()(int n, int m) {
		if (abs(n) > abs(m))
			return true;
		else if (abs(n) == abs(m)) {
			if (n > m)
				return true;
			else
				return false;
		}
		return false;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	priority_queue<int, vector<int>, avs> que; // 우선순위 큐 + 정렬방식 직접설정
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		if (x == 0) { // 쌓여있는 값 출력
			if (que.empty()) {
				cout << 0 << '\n';
			}
			else {
				cout << que.top() << '\n';
				que.pop();
			}
			continue;
		}
		else { // 0이 아닌 숫자이면 큐에 넣기
			que.push(x);
		}
	}

	return 0;
}

코드 리뷰는 언제나 환영입니다!