[BOJ] (Swift) 1158 - 요세푸스 문제

1158번: 요세푸스 문제

---

 

문제 요약

• N 명의 사람이 원을 이루며 앉아있고 K번째 사람을 제거하는 과정을 반복.
• 제거되는 사람의 순서를 출력하라.

 

풀이  1

• 1...N 이 들어있는 arr 배열에서 K 번째 원소를 제거해주는 과정을 반복한다.

import Foundation

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }

var N = input[0]
let K = input[1]
var arr = Array(1...N)
var result = [Int]()
var index = K - 1

while !(arr.isEmpty) {
    result.append(arr.remove(at: index))
    if arr.isEmpty { break }
    index = (index + (K - 1)) % arr.count
}

print("<" + result.map{ String($0) }.joined(separator: ", ") + ">")

• 손으로 테스트 케이스를 해보며 문제와 규칙을 이해했다.
• index 변수를 업데이트해주는 부분에서 시간이 오래 걸렸다. ( 쉬워서 금방 끝낼 줄 알았는데...ㅠㅠ)
• 처음엔 이런 식으로 index 변수를 업데이트해주었고 컴파일 에러가 발생했다.

 

풀이 2 ( Queue )

• 큐를 이용해서 풀어보았다.
• head를 K - 1만큼 이동하면서 사이의 숫자를 다시 enqueue 시키고, queue[head]를 result 배열에 추가한다.

struct Queue {
    var queue: [Int] = []
    var head: Int = 0
    
    public mutating func enqueue(_ element: Int) {
        queue.append(element)
    }
    
    public mutating func dequeue() -> Int{
        let element = queue[head]
        head += 1
        return element
    }
    
    public var count: Int {
        return queue.count
    }
}

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
var N = input[0]
let K = input[1]
var queue = Queue()
var result = [Int]()

for i in 1...N {
    queue.enqueue(i)
}

while queue.count - queue.head != 0 {
    for _ in 0..<(K-1) {
        queue.enqueue(queue.dequeue())
    }
    result.append(queue.dequeue())
}

print("<" + result.map{ String($0) }.joined(separator: ", ") + ">")

 

• 첫 번째 풀이보다 메모리 사용량이 높고, 시간도 오래 걸린다.