만득

코딩 공부 정리용

​

© 2021. All rights reserved.

백준 5430 AC

23 Jun 2021

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

R 뒤집기와 D 첫번째 숫자 버리기 라는 두 명령이 있는 언어가 주어지면 초기 배열에 적용한 최종 결과를 구하라.

deque를 활용하여 풀라고 되어있지만 swift에서는 front pop시 성능저하가 생겨서 다른 방법을 고안해야했다. 새로운 원소의 입력이 없기 때문에 배열에서 시작과 끝을 표시해주어 pop할때 실제로 pop하는 것이 아닌 index를 옮기는 방식으로 구현했다. reverse 여부에 따라 앞을 1 증가시킬지 뒤를 1 뺄지 결정하면 되는 문제이다.

단 error가 나는 case를 따로 고려해주어야 한다. 여기서는 first와 last가 역전되는 경우 error가 발생하도록 구현하였다.

let n = Int(readLine()!)!
loop: for _ in 1...n {
    let order = readLine()!
    let length = Int(readLine()!)!
    var testcase = readLine()!.split(separator: ",")
    if length == 0 {
        testcase = []
    }
    else {
        testcase[0].removeFirst()
        testcase[length-1].removeLast()
    }
    var deque = Deque(testcase.map{Int($0)!})
    for c in order {
        if deque.RD(str:c) {
            print("error")
            continue loop
        }
    }
    if deque.first > deque.last {
        print("[]")
    }
    else {
        var result = Array(deque.enqueue[deque.first...deque.last])
        if deque.reversed {result = result.reversed()}
        var str = "["
        for i in result {
            str += "\(i),"
        }
        str.removeLast()
        str += "]"
        print(str)
    }
}

struct Deque {
    var reversed:Bool = false
    var enqueue:[Int]
    var first:Int
    var last:Int
    init(_ arr: [Int]) {
        enqueue = arr
        first = 0
        last = arr.count-1
    }
    mutating func RD(str:Character) -> Bool {
        if str == "R" {
            reversed = !reversed
        }
        else if str == "D" {
            if first > last {
                return true
            }
            else {
                if reversed {
                    last -= 1
                }
                else {
                    first += 1
                }
            }
        }
        return false
    }
}

Related posts