[PS] 백준 1655 - 가운데를 말해요

DevHwan·2022년 4월 8일
0

BOJ

목록 보기
17/19
post-thumbnail

📌 알고리즘 분류


해당 문제는 Heap 자료구조에 대한 이해가 필요한 문제입니다.

📖 문제


백준 1655

💻 코드


특별한 알고리즘이 따로 적용되는 문제는 아닙니다. 우선순위 큐 자료구조를 이용하면 쉽게 해결할 수 있는 문제입니다. 문제의 설명 중 수 가 짝수개이면 그 중 작은 수를 출력하라는 내용이 있어서 출력형식을 맞게 작성합니다. max_heap에는 짝수개의 수 중에서 작은 수를 저장하고, min_heap에는 큰 수를 저장합니다.

다음과 같은 수의 입력이 들어왔을 때, 이해하기 쉽게 생각하면 이를 절반으로 나눕니다.

왼쪽처럼 빨간색을 max_heap에 저장하고, 오른쪽을 min_heap에 저장합니다. 그렇게 되면 자연스럽게 가운데 위치한 수가 max_heap의 top에 위치하게 되어서 결과를 출력할 수 있습니다.

📌 마무리


문제를 푼 지는 꽤 되었는 데, 가끔 보는 유형의 문제라서 정리해야겠다고 생각햇었는데 이제서야 정리를 하게 되었습니다.

profile
달리기 시작한 치타

0개의 댓글