[1021] 회전하는 큐

알고리즘 공부를 위해 풀었던 첫 백준문제이다. c++로 풀었는데, 이틀동안 문제만 들여다 보다가 결국 답을 검색하고나서 풀게되었다.

처음에 문제를 읽고나서도 이해가 안되서 지문을 수차례 읽었던 기억이 떠오른다. 이번에 스위프트로 재작성하여 공유해본다.

 

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

1021번: 회전하는 큐

 

풀이

큐의 변화는 크게 3가지이다.

1. 큐의 가장 첫번째 원소를 제거한다. 

2. 큐의 원소를 좌측으로 회전

3. 큐의 원소를 우측으로 회전

 

당시 고민했던 부분은 회전수를 최소화하는 것인데, 좌측의 회전수가 나오면 우측의 회전수는 자연스럽게 [큐의 크기 - 좌측회전수]를 통해 알수있게 되어 둘의 크기를 비교한 뒤 값이 적은 방향으로 이동하면 된다.

http://boj.kr/138f9df0ef054fbd8dc48e1fe2274c3d

//
//  main.swift
//  1021_swift
//
//  Created by Hyun on 2022/01/19.
//

import Foundation

let NM = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = NM[0]
let M = NM[1]
var q = Array(1...N)
var ans = 0

let targets = readLine()!.split(separator: " ").map{Int(String($0))!}
for target in targets{
    var left = 0
    var right = 0
    for idx in q.indices{
        if q[idx] == target{
            //회전수 계산하기
            left = idx
            right = q.count-idx
            break
        }
    }
    //회전수를 비교하여 적은 방향으로 회전하기
    if left < right{
        for _ in 0..<left{
            q.append(q.removeFirst())
            ans+=1
        }
    }else{
        for _ in 0..<right{
            q.insert(q.removeLast(), at: 0)
            ans+=1
        }
    }
    //원소 제거
    q.removeFirst()
}
print(ans)