백준 2220 힙 정렬 - Swift

 

https://www.acmicpc.net/problem/2220

2220번: 힙 정렬

 

문제

힙은 자료의 추가, 우선순위가 제일 높은 자료의 삭제가 가능한 자료구조이다. 이와 같은 힙에는 두 종류가 있는데, 각각 최소-힙, 최대-힙이다. 이 문제에서는 최대-힙을 다루기로 하자.

이와 같은 최대-힙을 이용하면 O(n log n)정렬인 힙 정렬을 할 수 있다. 우리가 다루기로 한 최대-힙을 이용하면 오름차순 정렬을 할 수 있다. 힙 정렬은 크게 두 개의 단계로 나뉘는데, 첫 번째 단계는 주어진 자료들로 힙을 구성하는 단계이고, 두 번째 단계는 이렇게 구성된 힙에서 최댓값을 계속 제거하는 단계이다.

예를 들어 (5, 4, 2, 1, 3)과 같은 힙을 살펴보자. 이 힙에서 최댓값을 삭제하면 (3, 4, 2, 1)이 되고, 힙의 조건을 맞추기 위해 Swap을 한 번 하면 (4, 3, 2, 1)의 힙을 얻는다. 이 힙에서 최댓값을 삭제하면 (1, 3, 2)이 되고, 힙의 조건을 맞추기 위해 Swap을 한 번 하면 (3, 1, 2)가 된다. 다음 단계에서는 (2, 1), (1)이 되고 힙 정렬이 종료된다. 즉, 힙이 (5, 4, 2, 1, 3)과 같이 구성되어 있었다면, 정렬을 위해 Swap을 두 번 사용하게 된다. 하지만 (5, 4, 3, 2, 1)과 같은 힙은 총 네 번의 Swap을 해야 한다.

n이 주어졌을 때, 1부터 n까지의 수를 한 번씩 사용하여 만들 수 있는 힙들 중에서, 위와 같은 Swap 회수가 최대가 되도록 하는 힙을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 100,000)

출력

첫째 줄에 n개의 정수로 힙을 출력한다.

예제 입력 1 

6

예제 출력 1

6 5 3 2 4 1

 

 

풀이 방법

최대 힙에서 Swap이 일어나는 경우를 생각해보면 자식 노드가 부모 노드 보다 클 때 Swap이 일어납니다.

그럼 Swap이 최대로 일어나려면 최소 값이 최대 힙의 꼭대기 자리에 있으면 되겠죠 ㅎㅎ!? 제일 밑까지 내려가야 하니까 

핵심 : 제일 마지막 자리에 제일 작은 수인 1을 고정 시켜 놓기

힙에 2 ~ n 까지 값을 힙에 차례대로 넣고 마지막에 1을 넣어주었습니다.

 

코드

struct PriorityQueue {
    var heap = [0]
    
    mutating func insert(_ element: Int) {
        heap.append(element)
        
        var currentIndex = self.heap.count - 1
        var parentsIndex = currentIndex / 2
        
        while canSwap() {
            self.heap.swapAt(currentIndex, parentsIndex)
            
            currentIndex = parentsIndex
            parentsIndex = currentIndex / 2
        }
        
        func canSwap() -> Bool {
            guard parentsIndex >= 1 else { return false }
            
            return heap[currentIndex] > heap[parentsIndex] ? true : false
        }
    }
}

var priorityQueue = PriorityQueue()
let n = Int(readLine()!)!
var answer = ""

func sol() {
    
    guard n > 1 else {
        print("1")
        return
    }
    
    for element in 2...n {
        priorityQueue.insert(element)
    }
    
    priorityQueue.heap.append(1)
    priorityQueue.heap.removeFirst()

    for i in priorityQueue.heap {
        answer += "\(i) "
        
    }

    answer.removeLast()
    print(answer)
}

sol()