백준 1021번 회전하는 큐 - SWIFT

문제

---

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 문제의 정답을 출력한다.

 

문제 링크

1021번: 회전하는 큐

 

풀이

---

이름에서도 알 수 있듯이 큐를 사용하는 문제이다.

그러나 원래 큐의 정의와는 약간 다르게 이 문제에서는 먼저 넣은 것과는 상관없이 무조건 맨 앞의 데이터를 pop할 수 있고, 데이터의 순서를 한 칸 씩 왼쪽, 오른쪽으로 밀 수 있다.

N과 M이 50 이하이기 때문에 50개의 원소를 50번 순회한다고 해도 단순 연산으로 2500번 밖에 되지 않으므로 별 상관이 없을 것이다. (실제로도 질문 검색을 보니 시간초과 질문은 하나도 없다.)

 

그래도 정말로 다 순회하는 방법은 사용하지 않았다.

대신 큐 자체를 돌리는게 아니라, 원형 큐라고 생각하고 맨 앞의 기준을 변경했다.▼

 

 

원형 큐로 생각하고 인덱스 계산하는 것은 약간의 % 연산이면 충분하다.

• 오른쪽 이동 : (인덱스 + 1) % 큐 크기
• 왼쪽 이동 : (인덱스 - 1 + 큐 크기) % 큐 크기

 

프로그램 동작

아래의 흐름을 따른다.

 

1. 현재 위치에서 왼쪽으로 가는게 더 빠른 지, 오른쪽으로 가는게 더 빠른 지 계산한다.

 

2. 둘 중 더 빠른 방향으로 이동한다.
이동할 때 몇 번 움직였는지 세준다.
몇 번 움직였는지가 곧 2번, 3번 연산의 횟수다.

 

 

3. 이동한 곳이 출력하려던 값이 맞다면, 해당 인덱스를 큐에서 제거해버린다.
여기서 주의할 점이 하나 있다.

잠시 선형 큐로 생각해보자.
이 쪽이 이걸 이해하기 더 좋다.
큐에서 원소를 제거하고 나면 맨 앞의 기준은 그대로인채로 모든 원소가 한 칸씩 앞당겨진다. ▼

 

 

지금같은 상황은 원소가 당겨지던 아무런 상관없이 정상적으로 동작한다.

하지만 맨 앞의 기준이 맨 끝값이라면 얘기가 다르다.▼

 

 

기준 점은 그대로인데 전체 원소가 줄었기 때문에 런타임 에러가 발생하게 된다.

이런 상황이 발생할 수 있기 때문에, 만약 큐의 원소가 0이 아닌 상황에서 맨 앞의 기준값이 큐 원소 개수랑 같다면 기준 값을 큐 원소 개수로 나머지 연산해주면 된다.

• 맨 앞의 기준 값 % 큐 원소 개수

그러면 맨 앞은 그대로 있는 것 처럼 보이고 맨 앞 값이 당겨져 온 것 처럼 된다.

 

 

4. 이를 원하는 값을 다 뽑을 때 까지 반복해주면 된다.

 

Swift 코드

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0]
let M = input[1]
var arr = readLine()!.split(separator: " ").map { Int(String($0))! }
var q = [Int]()
var pointer = 0
var answer = 0

func moveRight() {
    pointer = (pointer + 1) % q.count
}

func moveLeft() {
    pointer = (pointer - 1 + q.count) % q.count
}

for i in 0..<N {
    q.append(i)
}

for i in 0..<arr.count {
    var left = 0
    var right = 0
    if q.firstIndex(of: arr[i] - 1)! > pointer {
        right = q.firstIndex(of: arr[i] - 1)! - pointer
        left = pointer + q.count - q.firstIndex(of: arr[i] - 1)!
    } else if q.firstIndex(of: arr[i] - 1)! < pointer {
        left = pointer - q.firstIndex(of: arr[i] - 1)!
        right = q.firstIndex(of: arr[i] - 1)! + q.count - pointer
    }

    if min(right, left) == right {
        for _ in 0..<right {
            moveRight()
            answer += 1
        }
    } else if min(right, left) == left {
        for _ in 0..<left {
            moveLeft()
            answer += 1
        }
    }
    if q.firstIndex(of: arr[i] - 1) == pointer {
        q.remove(at: pointer)
        if q.count != 0 && pointer == q.count {
            pointer = pointer % q.count
        }
    }
}
print(answer)

 

사실 remove()함수는 안쓰는게 좋다.

전부 인덱스로 처리하는게 좋지만, 입력받는 수가 엄청 크지 않아서 그냥 사용했다.

어차피 2500정도밖에 연산안하는데 뭐 얼마나 줄이겠다고...

게다가 swift는 입력받는거랑 for문 도는 것만으로도 기본적으로 8ms를 소모한다.

remove() 썼는데도 8ms나온걸 보니 전혀 상관없는 거 같다.