백준 11866번 [요세푸스 문제 0](C++)-yes6686- 티스토리

백준 문제 풀이: 11866 [요세푸스 문제 0]

---

문제 링크: https://www.acmicpc.net/problem/11866

문제 설명:

1부터 n까지의 숫자가 원형으로 배열된 상태에서, k번째 사람을 제거하는 과정을 반복합니다. 이때 제거된 숫자들을 순서대로 출력하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue q;
    int n, k;
    cin >> n >> k;

    // 큐 초기화
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }

    cout << "<";

    // 요세푸스 순열 계산
    while (!q.empty()) {
        for (int j = 1; j < k; j++) {
            int a = q.front();
            q.pop();
            q.push(a);
        }
        if (q.size() > 1) {
            cout << q.front() << ", ";
            q.pop();
        } else {
            break;
        }
    }

    // 마지막 숫자 출력
    cout << q.front() << ">";
}

---

코드 설명

• 핵심 알고리즘: 큐를 활용하여 요세푸스 순열을 구현
• 구현 세부사항:
  • 큐에 1부터 n까지의 숫자를 삽입합니다.
  • k번째 숫자를 제거하기 위해, k-1개의 숫자를 큐의 뒤로 이동시킵니다.
  • k번째 숫자를 출력하며 큐에서 제거합니다.
  • 마지막 숫자를 처리하여 출력 형식을 맞춥니다.
• 시간 복잡도: O(n * k)
  • 큐의 크기가 n에서 1로 줄어드는 동안, k-1번의 연산이 반복됩니다.

---

결과

주어진 n과 k에 대해 요세푸스 순열을 계산하여 출력합니다. 큐를 활용한 간단한 구현으로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!