[C++ 알고리즘 풀이] 백준 1655번 가운데 수 말하기

[C++ 알고리즘 풀이] 백준 1655번 가운데 수 말하기

안녕하세요,

처음 포스팅 올립니다.

요즘 백준의 문제집 중 단기간 성장 편을 풀고 있는데, 문제들이 만만치 않네요.

이번에는 백준 1655번 가운데 수 말하기 문제를 풀어보았는데, 찾아보면서 푸는 거라 독창적인 저만의 아이디어는 없습니다. 다만 제 공부를 위해 블로그에 올리는 것인지라 많이 난잡합니다. 양해 부탁드립니다.

감사합니다.

#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); priority_queue maxheap; priority_queue, greater> minheap; int n; cin >> n; int x; for (int i = 0; i < n; i++) { cin >> x; if (maxheap.size() == 0) { maxheap.push(x); } else { if (maxheap.size() > minheap.size()) { minheap.push(x); } else { maxheap.push(x); } if (maxheap.top() > minheap.top()) { int maxtop = maxheap.top(); int mintop = minheap.top(); maxheap.pop(); minheap.pop(); maxheap.push(mintop); minheap.push(maxtop); } } cout << maxheap.top() << '

'; } return 0; }

중요한 것은, 생소할 수 있는 자료 구조인 deque, queue, priority queue 등의 queue 계열입니다.

아마 백준 티어 중 실버랑 골드/플레를 나누는 가장 큰 특징이 바로 이 계열의 자료 구조형들을 자유자재로 다룰 수 있는지 없는지일 것 같습니다.

이 자료구조형들에 대해 잠시 설명하자면,

덱은 보통 스케줄링에 많이 사용되는데 우선순위를 조절하게 될 때 유용합니다. 예를들어 먼저 있던 데이터에 우선순위를 두고 싶다면 앞에서 데이터를 빼내야하는데 이는 스택에서 불가능하고 최근에 들어온 데이터에 우선순위를 두고 싶다면 큐에서 불가능합니다.

add_front, delete_front 연산은 스택의 push, pop과 같은 연산이고 add_rear, delete_front 연산은 큐의 enqueue, dequeue 연산과 같습니다. 추가로 덱은 get_front, get_rear, delete_rear를 가지고 있습니다.

(참고: https://jongjineee.github.io/2019/10/28/deque.html)

반면 큐는 first-in-first-out (FIFO) 의 자료 구조형입니다. 좋은 예로 은행에 있는 번호표가 있습니다. 번호표 기계로 고객들에게 서비스를 효율적으로 운영하려면 서비스를 받을 처음 위치와 마지막의 위치만 기억하면 됩니다. 큐에서는 이것의 위치들을 각각 front, rear 라고 합니다. 큐는 값들에 대한 deletion, insertion 도 할 수 있는데, 다른 말로 dequeue, enqueue 라고 합니다.

정리를 해보면

(1) Enqueue : 큐 맨 뒤에 어떠한 요소를 추가, 마지막으로 온 손님에게 번호표 발부

(2) Dequeue : 큐 맨 앞쪽의 요소를 삭제, 창구에서 서비스를 받은 손님의 번호표를 대기목록에서 삭제

(3) Peek : front에 위치한 데이터를 읽음, 다음 서비스를 받을 손님이 누구인지 확인

(4) front : 큐의 맨 앞의 위치(인덱스), 다음 서비스를 받을 손님의 번호

(5) rear : 큐의 맨 뒤의 위치(인덱스), 마지막에 온 손님의 번호

(참고: https://monsieursongsong.tistory.com/5)

한편, 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말합니다.

주의해야할 점은, 우선순위 큐는 이름과는 달리 큐를 가지고 구현하지 않는다는 점입니다.

우선순위 큐는, 힙(heap) 을 가지고 구현합니다.

배열이나 연결 리스트가 삭제에서는 시간 복잡도의 우위를 점할지라도, 삽입의 시간 복잡도가 힙 기반이 월등하기 때문에, 편차가 심한 배열과 연결리스트보다는 힙으로 구현하는 것입니다.

힙은 Complete Binary Tree(완전 이진 트리) 이고 모든 노드에 저장된 값(우선순위)들은 자식 노드들의 것보다 (우선순위가) 크거나 같기 때문에 값의 크기 비교 시 직접 연결된 자식-부모 노드 간의 크기만 비교하면 됩니다.

이 힙을 이용해서 값이 작은 순서대로 우선순위가 생기는 최소합과, 값이 큰 순서대로 우선순위가 생기는 최대합을 구현한 것이 우선순위 큐입니다.

백준 1655번 문제 풀이의 경우 우선순위 큐를 생성한 후 노드들을 넣어준 후, 따로 예외적으로 중간값이 짝수일 경우, 즉 최대합의 최우선순위 값과 최소합의 최우선순위 값을 비교해서 더 작은 값이 최대합의 최우선순위 값이 되도록 바꾸어주었습니다.

감사합니다.

from http://unorthordox.tistory.com/8 by ccl(A) rewrite - 2021-10-04 23:00:20