[C++][Queue] 백준 1158번 : 요세푸스 문제

🏆 목차.

1. 문제
2. 코드
3. 풀이

 

🛒 문제

 

백준 1158번 요세푸스

 

🎨 코드

 

#include<iostream>
#include<queue>

using namespace std;

int main() {
    int n;
    int k;
    cin >> n >> k;
    queue<int> que;
    int curN = 0;
    for (int i = 1; i <= n; i++)
    {
        que.push(i);
    }
    cout << '<';
    while (!que.empty())
    {

        if (++curN % k == 0)
        {
            if(que.size() ==1)
                cout << que.front();
            else
                cout << que.front() << ", ";
            que.pop();
        }
        else
        {
            que.push(que.front());
            que.pop();
        }
    }
    cout << '>';
    return 0;

}

 

🎯 풀이

 

요세푸스 문제의 예시로 7과 3을 입력하면 다음과 같은 프로세스를 거치게 된다.

 

요세푸스 예시

 

n이 7이고 k가 3일 때,

3번째 요소가 front에 있다면 출력하고 삭제시켜야 하고

3번째가 아니라면 뒤로 다시 옮긴다.

 

위 사진에서 3이 front에 왔고 3번째 요소이므로 삭제를 시킨다.

계속해서 6이 front에 오면 삭제시키고,

다음 2가 front에 오면 삭제된다.

 

이런 방식으로 반복하면 3번째 요소는 계속해서 출력되고 마지막에는 아무 값도 남지 않게 된다.

 

++curN % k == 0

해당 코드를 이용해  k와 curN의 나머지값이 0 일 때 지정한 순서로 인식하고 값을 삭제되도록 했다.