글 읽기 - Swift 시간초과 해결 팁

esl112999 2년 전 2

7576문제와 더불어 토마토 문제는 대개 시간초과나는 이유는 로직이 아닌 입출력과, dequeue 중에 있다고 생각합니다.

1. 파일 입출력 관련 -> readline() 이 아닌 FileIo.readInt()를 이용했습니다.

https://gist.github.com/JCSooH...

2. Queue문제, Array에서의 removeFirst는 O(n)입니다. -> LinkedList나 DoubleStackQueue 이용
저는 DoubleStackQueue를 이용하였습니다. 코드는 아래 첨부토록 하겠습니다.

도움이 될만한 구조체 부분만 첨부했습니다! 화이틩

건승하세용

struct DoubleStackQueue<Element> {
    private var inbox: [Element] = []
    private var outbox: [Element] = []
    
    var isEmpty: Bool{
        return inbox.isEmpty && outbox.isEmpty
    }
    
    var count: Int{
        return inbox.count + outbox.count
    }
    
    var front: Element? {
        return outbox.last ?? inbox.first
    }
    
    init() { }
    
    init(_ array: [Element]) {
        self.init()
        self.inbox = array
    }
    
    mutating func enqueue(_ n: Element) {
        inbox.append(n)
    }
    
    mutating func dequeue() -> Element {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox.removeAll()
        }
        return outbox.removeLast()
    }
}

extension DoubleStackQueue: ExpressibleByArrayLiteral {
    init(arrayLiteral elements: Element...) {
        self.init()
        inbox = elements
    }
}

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

문제

문제

출처

ICPC

Swift 시간초과 해결 팁

esl112999 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말