1158번: 요세푸스 문제

Queue를 활용해서 푸는 방법

// 요세푸스 문제

/*
 # 써야할 자료구조 = queue
     : 원을 나타내는 자료구조는 없으므로 원을 일자로 펴서 표현해야 합니다.
     : 한 사람이 제거되면 제거된 사람이 첫 번째 사람이 되어서 k번째 사람을 제거합니다.
     : 따라서 앞에서 pop하고 뒤에 push하는 방식으로 k번째 사람을 구하므로 queue 자료형을 사용합니다.

 # 문제 풀이 아이디어
     : 1 ~ n의 queue를 만들어 원을 표현합니다.
     : k번째 사람을 제거하는 것을 queue에서 queue.push(queue.pop())을 k - 1번 수행하고 pop하는 것으로 구현

 # 의사코드
     1. 인풋을 받아서 1 ~ n의 queue를 만든다.
     2. while문을 사용해서 dq의 길이가 0 보다 큰 동안 실행합니다.
         2-1. queue에서 pop한 것을 다시 queue에 push하는 것을 k - 1번 실행합니다.
         2-2. 그리고 pop한 것을 빈 Array에 저장해둡니다.
     3. 배열을 양식에 맞게 순서대로 출력합니다.

 # 시간복잡도
     : while 반복문 내부의 코드를 총 n번 실행됩니다.
     : 그 내부에 있는 반복문은 k번 실행됩니다. (queue 연산은 O(1))
     : O(n**2)이 예상됩니다. n이 최대 5000이므로 시간 내에 해결이 가능합니다.
 */

// 큐 구현
struct Queue {
    var data = [Int]()
    var index = 0
    
    var count: Int {
        return data.count - index
    }
    
    mutating func push(_ n: Int) {
        data.append(n)
    }
    
    mutating func pop() -> Int {
        defer {
            index += 1
        }
        return data[index]
    }
}

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

(1...N).forEach { i in
    queue.push(i)
}

// 결과 저장 배열
var result = [Int]()

// K번째 제거 = (K - 1번 push&pop) + pop
while queue.count != 0 {
    for _ in 0..<(K - 1) {
        queue.push(queue.pop())
    }
    result.append(queue.pop())
}

// [String]를 joined로 출력하기
print("<" + result.map { String($0) }.joined(separator: ", ") + ">")

나머지를 활용해서 푸는 방법

Swift에서는 Queue를 직접 구현해야하기 때문에 index를 추적해가면서 푸는 방식이 더 간단한 방식입니다.

시간 복잡도는 동일하게 O(n**2)입니다.

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

// 원 Array 만들기
var circle = [Int]()
for i in 1...N {
    circle.append(i)
}

// 결과 저장 배열
var result = [Int]()

// 제거 대상의 index
var toRemove = K - 1

// toRemove에 있는 element를 제거하고
// 다음 toRemove를 구할 때 K - 1을 더하고 현재 원의 길이로 나누어 준다. (한바퀴 돌면 제자리)
while true { //👉 O(n)
    result.append(circle.remove(at: toRemove)) // 👉 O(n)
    if circle.isEmpty { break }
    toRemove = (toRemove + (K - 1)) % circle.count
}

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