백준 11866 요세푸스 문제 Swift

요세푸스 순열(Josephus permutation)은 고전적인 문제로, 다음과 같은 상황에서 유래된 문제입니다:

문제 설명

한 그룹의 사람들이 원형으로 앉아 있고, 특정 번호를 가진 사람부터 시작해, 지정된 숫자에 따라 하나씩 건너뛰며 사람을 제거합니다. 이 과정을 마지막 한 명이 남을 때까지 반복합니다. 이 과정에서 제거되는 사람들의 순서를 요세푸스 순열이라고 합니다.

예시

예를 들어, 7명의 사람이 있고, 3번째 사람마다 제거된다고 합시다. 순열은 다음과 같이 진행됩니다:

• 초기 상태: 1, 2, 3, 4, 5, 6, 7
• 첫 번째 제거: 3 -> 남은 사람: 1, 2, 4, 5, 6, 7
• 두 번째 제거: 6 -> 남은 사람: 1, 2, 4, 5, 7
• 세 번째 제거: 2 -> 남은 사람: 1, 4, 5, 7
• 네 번째 제거: 7 -> 남은 사람: 1, 4, 5
• 다섯 번째 제거: 5 -> 남은 사람: 1, 4
• 여섯 번째 제거: 1 -> 남은 사람: 4
• 마지막 남은 사람: 4

따라서 요세푸스 순열은 [3, 6, 2, 7, 5, 1, 4]입니다.

알고리즘

이 문제를 해결하기 위해 일반적으로 원형 큐나 리스트를 사용합니다. 각 사람을 리스트에 배치한 후, 주어진 간격에 따라 사람을 제거하고, 리스트를 업데이트하는 방식으로 문제를 해결합니다.

Swift로 구현

다음은 요세푸스 순열을 계산하는 Swift 코드입니다:

func josephus(n: Int, k: Int) -> [Int] {
    var result = [Int]()
    var people = Array(1...n)
    var index = 0

    while !people.isEmpty {
        index = (index + k - 1) % people.count
        result.append(people.remove(at: index))
    }

    return result
}

// 예시 실행
let n = 7
let k = 3
let result = josephus(n: n, k: k)
print(result)  // 출력: [3, 6, 2, 7, 5, 1, 4]

코드 설명

1. people 배열: 1부터 n까지의 숫자를 담은 배열입니다. 이 배열에서 하나씩 사람을 제거해 나갑니다.
2. index 변수: 제거할 사람의 인덱스를 추적합니다. 인덱스는 (index + k - 1) % people.count로 계산됩니다. 이 수식은 원형 구조를 구현하며, 항상 범위를 넘지 않도록 해줍니다.
3. 결과 저장: 제거된 사람을 result 배열에 순서대로 저장합니다.
4. 반복문: 모든 사람이 제거될 때까지 계속해서 반복합니다.

이 코드를 통해 주어진 n과 k에 대해 요세푸스 순열을 쉽게 구할 수 있습니다.

---

이와 같은 코드를 생각해내기 위해서는 문제의 구조를 이해하고, 문제를 단계별로 해결하는 방법을 생각해내는 것이 중요합니다. 여기서는 주어진 문제를 해결하기 위해 index 변수를 사용하여 제거할 사람의 위치를 계산하는 과정을 설명하겠습니다.

1. 문제 구조 이해

요세푸스 문제의 핵심은 원형 구조에서 사람을 특정 간격(k)으로 제거하는 것입니다. 이때 원형 구조는 끝이 다시 처음과 연결된 구조입니다. 배열을 사용해 원형 구조를 구현할 때, 인덱스를 사용하여 위치를 추적할 수 있습니다.

2. 원형 구조를 배열로 표현하기

배열을 사용하면 각 사람을 쉽게 관리할 수 있습니다. 예를 들어, 7명의 사람을 [1, 2, 3, 4, 5, 6, 7]로 표현할 수 있습니다.

3. 인덱스를 사용하여 위치 추적

제거할 사람의 위치를 찾기 위해 인덱스를 사용합니다. 첫 번째 사람을 제거한 후에는 다음 사람이 기준이 됩니다. 그리고 다음 사람을 찾을 때는 간격 k만큼 떨어진 위치에서 사람을 제거해야 합니다.

4. 인덱스 계산 방식

인덱스를 사용하여 위치를 추적할 때, 현재 인덱스에서 k-1만큼 이동한 위치의 사람을 제거하면 됩니다. k-1을 더하는 이유는 현재 위치를 포함하지 않고 다음 위치를 고려하기 위해서입니다. 예를 들어:

• 첫 번째 사람(인덱스 0)에서 k-1만큼 이동하면 제거할 사람의 위치를 정확히 알 수 있습니다.
• 이때, 원형 배열이므로 배열의 끝에 도달했을 때는 다시 처음으로 돌아가야 합니다. 이것이 (index + k - 1) % people.count의 의미입니다. % 연산은 배열의 끝에 도달했을 때 다시 처음으로 돌아가도록 인덱스를 조정해 줍니다.

5. 순서대로 제거하기

각 제거 단계에서 다음 인덱스를 계산하고, 그 인덱스에 있는 사람을 배열에서 제거하면 됩니다. 그 후, 남은 사람들에 대해 다시 같은 방법을 반복합니다. 이 과정을 반복하면 모든 사람을 제거할 수 있습니다.

6. 코드로 구현

var index = 0
index = (index + k - 1) % people.count

이 코드를 보면:

1. index는 현재 제거할 사람의 위치를 나타냅니다.
2. (index + k - 1)는 현재 위치에서 k-1만큼 이동한 위치를 계산합니다.
3. % people.count는 배열의 끝에 도달했을 때 다시 처음으로 돌아가도록 인덱스를 조정합니다.

7. 전체 과정

이 과정을 전체적으로 반복하면 각 단계에서 정확한 사람을 제거할 수 있고, 이때 제거된 사람들의 순서가 요세푸스 순열이 됩니다.

요약

• 문제를 원형 배열로 생각합니다.
• 인덱스를 통해 제거할 사람의 위치를 계산합니다.
• % 연산을 사용해 원형 구조를 유지합니다.
• 이 과정들을 반복하여 요세푸스 순열을 완성합니다.

이러한 방식은 문제를 여러 작은 단계로 나누어 해결하는 데 도움이 됩니다. 각 단계가 문제를 어떻게 해결하는지 이해하면, 더 복잡한 문제도 비슷한 방식으로 접근할 수 있습니다.