Baekjoon_1158_요세푸스 문제

문제주소: https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

요세푸스 문제에 대한 설명이 문제에도 있지만, 다음 링크를 보시면 조금 더 이해하기 쉬울 수 있습니다.

요세푸스: https://ko.wikipedia.org/wiki/%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4_%EB%AC%B8%EC%A0%9C

요세푸스 문제 - 위키백과, 우리 모두의 백과사전

이를 해결하기 위해 queue를 사용하였으며, 입력한 순서가 될 때까지 앞쪽 번호를 뒤쪽으로 옮기고 입력한 순서가 된다면, 빈 list에 담도록 하였습니다.

---

init_list: [1, 2, 3, 4, 5, 6, 7], answer: []

1. init_list: [1, 2, 3, 4, 5, 6, 7], answer: [] → init_list: [2, 3, 4, 5, 6, 7, 1], answer: []
2. init_list: [2, 3, 4, 5, 6, 7, 1], answer: [] → init_list: [3, 4, 5, 6, 7, 1, 2], answer: []
3. init_list: [3, 4, 5, 6, 7, 1, 2], answer: [] → init_list: [4, 5, 6, 7, 1, 2], answer: [3]

---

코드는 다음과 같습니다.

Python

import sys
from collections import deque

def main():
    max_num, rep_num = sys.stdin.readline().split(' ')
    max_num: int = int(max_num)
    rep_num: int = int(rep_num)

    my_queue: deque[int] = deque()
    my_answer: list[int] = []

    check_num: int = 1

    # make my_queue
    for i in range(max_num):
        my_queue.append(i+1)

    # Josephus
    while(my_queue):
        if (check_num%rep_num == 0):
            my_answer.append(my_queue.popleft())
            check_num = 0

        else:
            my_queue.append(my_queue.popleft())

        check_num += 1

    total_answer = "<"+', '.join(str(number) for number in my_answer)+">"
    print(total_answer)

if __name__ == "__main__":
    main()

 

C++

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio;
    cin.tie(), cout.tie();

    int last_num, repeat_num;
    int check_num = 1;
    int first_num;

    // input
    cin >> last_num >> repeat_num;

    queue<int> my_que;
    vector<int> answer; // queue는 index 탐색이 안되기 때문에 vector 사용

    for (int i=1; i<=last_num; i++)
        my_que.push(i);
    
    while(!my_que.empty())
    {
        if (check_num%repeat_num == 0)
        {
            first_num = my_que.front(); // first num return
            my_que.pop(); // remove first num
            answer.push_back(first_num); // add data in answer

            check_num = 0; // initialization
        }
        else if (!my_que.empty())
        {
            first_num = my_que.front(); // first num return
            my_que.pop(); // remove first num
            my_que.push(first_num); // add data in my_que
        }
        else
        {
            break;
        }

        check_num++;
    }
    // output
    cout << "<";

    for (int i=0; i<answer.size(); i++)
    {
        cout << answer[i];
        
        if (i != answer.size()-1)
            cout << ", ";
    }
    cout << ">";
}