[Swift 알고리즘] 백준_11279 (최대 힙)

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

11279번: 최대 힙

 

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

해결 방법 :
먼저 처음 생각한 방법은 입력 받는 값을 트리 형태로 정렬이다.

이를 해결하기 위해 start, mid, end라는 변수로

현재 인풋 값과 arr값들을 비교한다. 대충 설명해 보자면

let target = readLIne()!
var stat = 0, mid = 0, end = arr.count
while end - start > 0 {
     mid = (start + end) / 2
     if arr[mid] < target {
          start = mid + 1
     } else {end = mid}
}
arr = arr[..<start] + [target] + [start...]

바로 시간초과 나서 부들부들 거렸다.

아마 removeFist()와 arr을 갱신해주는 곳에서 에러가 난 듯...

import Foundation

func sol() {
    let inputN: Int = Int(readLine()!)!
    var curHeap: [Int] = []
    for _ in 0..<inputN {
        let curInput = Int(readLine()!)!
        if curInput == 0 {
            if curHeap.isEmpty {
                print(0)
            }else {
                print(curHeap.removeFirst())
            }
        }else {
            var start = 0
            var end = curHeap.count
            var mid = start
            while end - start > 0 {
                mid = (start + end) / 2
                if curHeap[mid] < curInput {
                    end = mid
                }else {start = mid + 1}
            }
            curHeap = curHeap[..<end] + [curInput] + curHeap[end...]
        }
    }
}
sol()

 

그래서 그냥 removeFIst()를 제외한 map을 활용한 코드를 써 보았다.

func sol2() {
    let inputN: Int = Int(readLine()!)!
    var curHeap: [Int] = []

    for _ in 0..<inputN {
        let curInput = Int(readLine()!)!
        if curInput == 0 {
            if curHeap.isEmpty {
                print(0)
            }else {
                var tempMax = -1
                var tempInd = 0
                curHeap.enumerated().map{ (ind, val) in
                    if tempMax < val {
                        tempMax = val
                        tempInd = ind
                    }
                }
                curHeap[tempInd] = 0
                print(tempMax)
            }
        }else {
            curHeap.append(curInput)
        }
    }
}
sol2()

시간초과...

 

그냥 너무 화나서 더럽게 코딩하니까 그제서야 정답 인정... 음... 자료구조 문제는 너무 빡빡한 것 같다.

func sol2() {
    let inputN: Int = Int(readLine()!)!
    var curHeap: [Int] = []

    for _ in 0..<inputN {
        let curInput = Int(readLine()!)!
        if curInput == 0 {
            if curHeap.isEmpty {
                print(0)
            }else {
                var tempMax = -1
                var tempInd = 0
                for (ind ,val) in curHeap.enumerated() {
                    if tempMax < val {
                        tempMax = val
                        tempInd = ind
                    }
                }
                curHeap[tempInd] = 0
                print(tempMax)
            }
        }else {
            curHeap.append(curInput)
        }
    }
}
sol2()