글 읽기 - Swift priority_queue 속도가 느리네요....

QuqqU 6년 전 0

아래에 있는 소스로 수 정렬하기1 문제는 맞았는데,

수 정렬하기2 문제부터는 시간초과가 뜨네요...

swift가 그렇게 느린 언어도 아니고, 분명 heap을 제대로 구현한 것 같은데

왜 시간초과가 날까요...?

수정렬하기1을 맞아서 내부 구현은 맞는 거 같은데.... 아시는 분 계신가요?

//: Playground - noun: a place where people can play

import Foundation

class PriorityQueue<T: Comparable> {
    private var _heap = [T]()
    private let order: (T, T) -> Bool
    
    
    init(array: [T], ascending: Bool) {
        order = ascending ? { $0 < $1 } : { $0 > $1 }
        
        for i in 0..<array.count {
            self.push(value: array[i])
        }
    }
    
    public func push(value: T) {
        self._heap.append(value)
        var idx = self._heap.count - 1
        while idx > 0 {
            if order(_heap[idx], _heap[(idx-1)/2]) {
                _heap.swapAt(idx, (idx-1)/2)
            }
            idx = (idx-1)/2
        }
    }
    
    public func pop() -> T? {
        if self.isEmpty {
            return nil
        }
        self._heap.swapAt(0, self.count-1)
        
        var curr = 0
        reviseHeap : while true {
            let left = (curr+1)*2 - 1;
            let right = (curr+1)*2;
            var c = curr;
            
            if left < self.count - 1 && order(self._heap[left], self._heap[c]) { c = left }
            if right < self.count - 1 && order(self._heap[right], self._heap[c]) { c = right }
            if c == curr { break reviseHeap }
            
            _heap.swapAt(curr, c)
            curr = c
        }
        
        return self._heap.removeLast()
    }
    
    public func top() -> T? {
        if self.isEmpty {
            return nil
        }
        return self._heap.first
    }
    
    public func clear() {
        self._heap.removeAll(keepingCapacity: false)
    }
    public var heap: [T] {
        return self._heap
    }
    public var count: Int {
        return self._heap.count
    }
    public var isEmpty: Bool {
        return self._heap.isEmpty
    }
    
}


extension PriorityQueue {
    convenience init() {
        self.init(array: [], ascending: false)
    }
    convenience init(array: [T]) {
        self.init(array: array, ascending: false)
    }
    convenience init(ascending: Bool) {
        self.init(array: [], ascending: ascending)
    }
}

let pq:PriorityQueue<Int> = PriorityQueue(ascending: true)

let n = Int(readLine()!)!
for _ in 0..<n {
    let a = Int(readLine()!)!
    pq.push(value: a)
}

while !pq.isEmpty {
    print(pq.pop()!)
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Swift priority_queue 속도가 느리네요....

QuqqU 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말