[백준] 1655.가운데를 말해요 (Swift)

코딩테스트/백준

도지대디 2022. 5. 24. 01:32

1655번: 가운데를 말해요

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1

www.acmicpc.net

풀이

시간복잡도를 고려해야하기 때문에 힙을 사용하는 문제입니다.

풀이를 위해선 최대힙과 최소힙을 모두 사용하는데, Swift 는 힙 자료구조를 제공하지 않아 직접 구현해야 합니다.

힙에 관한 설명과 Swift 를 이용해 작성된 코드는 아래 링크에서 확인하실 수 있습니다.

[자료구조] Swift 로 Heap 구현하기

[자료구조] Swift 로 Heap 구현하기 Heap 은 이진트리 형태의 자료구조로 최대값 및 최소값을 빠르게 탐색할수 있도록 설계되었습니다. Heap 에는 2가지 종류가 있는데, 부모노드의 키값이 자식노드의

trumanfromkorea.tistory.com

중간값을 찾기 위해서 최소힙과 최대힙에 번갈아가며 원소를 삽입해줍니다.

이 때 최대힙의 모든 원소가 최소힙보다 작은 값을 유지하도록 신경써주는것이 핵심입니다.

그렇게 된다면 최대힙의 루트노드는 최소힙보다는 작지만, 최대힙의 다른 모든 노드들보다 큰 값을 가지기 때문에 중간값을 도출해낼 수 있습니다.

힙의 원소 삽입과 삭제는 O(logN) 의 시간복잡도를 가지기 때문에 단순히 정렬하여 중간값을 뽑는 것 보다 효율적으로 문제를 풀이할 수 있습니다.