백준 11866 요세푸스 문제 0
23 Jun 2021https://www.acmicpc.net/problem/11866
원에 1-N번의 사람이 순서대로 앉아 있을 때 K번째 사람을 제거하고 남은 사람들로 이루어진 원을 따라 계속해서 K번째 사람을 제거해나간다고 했을 때 제거되는 사람 순서를 (N, K) - 요세푸스 순열이라고 부른다. n과 k가 주어졌을 때 요세푸스 순열을 구하는 문제이다.
여기서는 큐를 활용한 문제이기 때문에 queue로 구현했다. 1-N 들어있는 큐에서 반복적으로 pop한 후 해당 값을 다시 push한다. 만약 K번째에 해당한다면 그 값을 pop한 후 순열에 저장한다. 이 값은 다시 큐에 넣지 않는다.
swift에서는 pop이 O(n)의 시간이 걸리기 때문에 속도단축을 위해서 enqueue와 dequeue를 활용해서 구현했다. 문제에서 요구하는 형식에 맞게 출력을 수정하는 것을 잊지 않도록 하자.
- 전체 코드
struct Queue {
var enqueue:[Int] = []
var dequeue:[Int] = []
init(_ arr:[Int]) {
enqueue = arr
}
mutating func push(_ a: Int) {
enqueue.append(a)
}
mutating func pop() -> Int {
if dequeue.isEmpty {
dequeue = enqueue.reversed()
enqueue.removeAll()
}
if dequeue.isEmpty {
return -1
}
else {return dequeue.removeLast()}
}
}
let nk = readLine()!.split(separator: " ").map{Int($0)!}
let n = nk[0]
let k = nk[1]
var queue = Queue([Int](1...n))
var str = "<"
for _ in 1...n {
for _ in 1..<k {
queue.push(queue.pop())
}
str += "\(queue.pop()), "
}
str.removeLast()
str.removeLast()
str += ">"
print(str)