1021번: 회전하는 큐

🤔 어떻게 풀어야 할까?

써야할 자료구조 = deque

: Double-Ended Queue = 앞뒤로 모두 pop할 수 있는 queue

: 일단 맨 앞에서 원소를 뽑아내야 하므로 선입후출 방식을 큐를 써야 합니다.
: 추가적으로 왼쪽 이동, 오른쪽 이동 연산도 원소를 pop 앞 or 뒤에 push한 것입니다.
: 세 가지 연산을 모두 O(1)로 할 수 있는 deque 자료구조를 사용합시다.

문제풀이 아이디어

1. 먼저 뽑아낼 수 있는 원소는 0번째 인덱스이므로 0번째 인덱스로 원하는 수를 보내야합니다.
2. 왼쪽 한칸 vs 오른쪽 한칸 연산 중에 더 빠른 연산을 골라서 해야 합니다.
3. 큐의 현재 상태를 저장하면서 pop할 원소의 index를 추적해야합니다.

의사코드

1. 인풋을 받는다, 두 번째 줄은 배열로 저장합니다.
2. 1 ~ n까지 deque를 선언합니다.
3. 배열에서 하나씩 빼서 반복문을 돌립니다.
   3 - 1. 왼쪽 한칸 vs 오른쪽 한칸 중에 더 적게 필요한 것을 고릅니다.
   : (현재 목표 원소의 인덱스) vs (큐의 길이 - 현재 인덱스)를 비교합니다.
   3 - 2. 반복문으로 연산을 실제로 실시하고 연산 횟수는 cnt에 저장합니다.
4. cnt를 출력합니다.

시간 복잡도

: 먼저 M만큼 반복문 1개
: 그 반복문 안에서 큐의 연산을 실제로 수행하는 반복문 1개로 (내부의 dq 연산은 O(1))
: O(N**2)이 예상됩니다. n은 최대 50이므로 시간 내에 해결이 가능합니다.

풀이

Deque 구현하기

// 데큐 구현
struct Deque {
    //✅ deque를 구현할 때는 무조건 더블 스택큐를 사용합니다.
    var input = [Int]()
    var output = [Int]()
    
    var count: Int {
        return input.count + output.count
    }
    
    //✅ queue에서 특정 값의 index를 구하는 함수
    func index(of n: Int) -> Int {
        let queue = output.reversed() + input // 원래 queue 모양대로 만들어서
        return queue.firstIndex(of: n)! // index를 구해서 리턴
    }
    
    //✅ 오른쪽에 push = 원래 queue와 동일하게 구현
    mutating func pushRight(_ n: Int) {
        input.append(n)
    }
    
    //✅ 왼쪽에 push
        // = queue에서 바로 pop될 자리
        // = output의 맨 뒤에 넣으면 됨
    mutating func pushLeft(_ n: Int) {
        output.append(n)
    }
    
    //✅ 왼쪽에서 pop = 원래 queue와 동일하게 구현
    mutating func popLeft() -> Int {
        if output.isEmpty {
            output = input.reversed()
            input.removeAll()
        }
        return output.popLast()!
    }
    
    //✅ 오른쪽에서 pop
        // = queue에서 방금 push된 자리
        // input의 맨 마지막꺼 빼면 됨
    mutating func popRight() -> Int {
        if input.isEmpty {
            input = output.reversed()
            output.removeAll()
        }
        return input.popLast()!
    }
}

문제 풀이

//✅ 문제 풀이를 위한 메소드 구현
extension Deque {
    mutating func moveLeft() {
        self.pushRight(self.popLeft())
    }
    
    mutating func moveRight() {
        self.pushLeft(self.popRight())
    }
}

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1]
let toPops = readLine()!.split(separator: " ").map { Int(String($0))! }

// deque 만들기
var deque = Deque()
for i in 1...N {
    deque.pushRight(i)
}

// 2, 3번 연산 횟수를 저장할 변수
var cnt = 0

// pop 해야할 수 반복문
toPops.forEach { toPop in
    let moveLeftCount = deque.index(of: toPop) //👉 왼쪽으로 옮겨서 뺄 때 횟수
    let moveRightCount = deque.count - moveLeftCount //👉 오른쪽으로 옮겨서 뺄 때 횟수

    // 더 적은 쪽으로 선택해서 빼기
    if moveLeftCount < moveRightCount {
        for _ in 0..<moveLeftCount {
            deque.moveLeft()
        }
        _ = deque.popLeft()
        cnt += moveLeftCount
    } else {
        for _ in 0..<moveRightCount {
            deque.moveRight()
        }
        _ = deque.popLeft()
        cnt += moveRightCount
    }
}

print(cnt)