[BOJ, Swift] 1021 - 회전하는 큐 ( with 덱(Dequeue) )

1021번: 회전하는 큐

추가하는 건 맨 뒤에서, 빼는 건 양쪽 방향에서 해줄 수 있는 큐가 필요하다. 덱(double ended queue)을 구현해주면 되는데, 해당 문제에서는 양방향으로 추가해줄 필요가 없어서 기존에 구현했던 큐를 일부 수정, 변형하였다.

 

회전하는 큐 구현

struct Queue {
    var left = [Int]()
    var right = [Int]()
    
    var count: Int {
        left.count + right.count
    }
    
    var isEmpty: Bool {
        left.isEmpty && right.isEmpty
    }
    
    // 첫번째 값
    var first: Int? {
        guard !isEmpty else { return -1 }
        return right.isEmpty ? left.first : right.last
    }
    
    // 인덱스
    func index(_ value: Int) -> Int {
    
    	// 오른쪽이 비어있으면 왼쪽에서만 인덱스가 필요
        if right.isEmpty {
            return left.firstIndex(of: value)!
        } else {
			// 오른쪽에 값이 존재하면 오른쪽에서만 인덱스 구하기
            if right.contains(value) {
                return right.count - right.firstIndex(of: value)! - 1
            
			// 왼쪽에 존재하면 오른쪽 값의 개수 + 왼쪽 인덱스
            } else {
                return right.count + left.firstIndex(of: value)!
            }
        }
    }
    
    // 값 추가
    mutating func enqueue(_ value: Int) {
        left.append(value)
    }
    
    // 선입선출에 사용, 오른쪽이 비어있으면 왼쪽 값으로 채워주고 마지막을 빼줌
    mutating func popLeft() -> Int {
        if right.isEmpty {
            right = left.reversed()
            left.removeAll()
        }
        return right.removeLast()
    }
    
    // 후입선출에 사용, 왼쪽 값이 있으면 왼쪽에서 바로 빼고, 없으면 오른쪽을 왼쪽 값으로 채워서 빼준 후 원상복귀
    mutating func popRight() {
        if !left.isEmpty {
            right.append(left.removeLast())
        } else {
            left = right.reversed()
            let last = left.removeLast()
            right = left.reversed()
            right.append(last)
            left.removeAll()
        }
        
    }
    
    // PS에서 배열을 통째로 집어넣을 때 사용, 구조체에 초기화를 구현해도 좋음.
    mutating func add(_ value: [Int]) {
        left += value
    }
}

문제에 맞게 큐 핸들링

var dq = Queue()
let input = readLine()!.split { $0 == " " }.map { Int(String($0))! }
dq.add(Array<Int>(1...input[0]))
var order = readLine()!.split { $0 == " " }.map { Int(String($0))! }

var count = 0
for idx in order {

	// idx가 dq의 첫번째와 같을 때는 바로 빼줌
    if dq.first == idx {
        dq.popLeft()
    } else {
    
    	// idx가 왼쪽에 가까운지, 오른쪽에 가까운지 비교
        if dq.index(idx) <= dq.count / 2 {
            while dq.first != idx {
                dq.enqueue(dq.popLeft())
                count += 1
            }
        } else {
            while dq.first != idx {
                dq.popRight()
                count += 1
            }
        }
        dq.popLeft()
    }
}
print(count)