[BOJ/C++] 요세푸스 문제(1158번)

1. 개요

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

1-1. 설명

1번부터 N번까지 N명의 사람이 원을 이루어 앉아있고 양의 정수 K가 주어진다.이제 순서대로 K번째 사람을 제거한다. 한사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 이러한 요세푸스 순열을 구현하는 프로그램을 작성한다.

1-2. 제한 사항

 - 첫줄에 N과 K가 주어짐

 - 1 <= K <= N <= 5,000

---

2. 구현

2-1. 풀이

원래는 배열에 정수를 차례대로 저장해 일일히 찾으면서 했으나, 시간 초과가 나타나면서 queue로 변경하여 진행하게 되었다. queue에 차례대로 정수를 저장하고, K주기로 K가 되기 전엔 다시 queue 뒤로 넣어주며, K번째가 되었을때 result에 저장한다.

2-2. 코드

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

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, K, num, index = 0;
    cin >> N >> K;

    queue<int> que;

    for (int i = 0; i < N; i++) que.push(i + 1); // 1 ~ N 정수 차례대로 저장

    cout << '<';
    while (true) {
        if (que.empty()) break; // 큐가 비면 while 종료

        num = que.front(); // 맨 앞부분 저장
        que.pop();
        index += 1;
        if (index == K) { // K번 이동했을 때
            index = 0;
            if (!que.empty()) cout << num << ", "; // 마지막 정수일 때
            else cout << num;
            continue;
        }
        que.push(num); // 다시 뒤로 보냄

    }
    cout << '>';

    return 0;
}