[BOJ알고리즘, C++]#1158_요세푸스 문제, 선형 자료구조, 큐

 

[BOJ알고리즘, C++]#1158_요세푸스 문제

 

BOJ 알고리즘 문제 풀이, 1158번 문제 "요세푸스 문제"

C++의 STL이 제공하는 queue 컨테이너를 활용하는 문제

 

---

 

Overview

 

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

 

#1. 문제

 

#2. 풀이

1. 큐

[자료 구조]#0_선형 자료구조

 

• [정의] : 큐는 선입선출 방식으로 동작하는 선형 자료입니다. 동일한 크기와 유형의 데이터를 데이터 목록의 한쪽 방향에선 '삽입'하며, 다른 한쪽에선 '제거'합니다.

 

2. queue 컨테이너

[Basic C++] #67_queue

 

3. queue 컨테이너를 활용한 원소 재배치

1. 먼저, 입력으로 받은 원소들을 모두 queue 컨테이너에 차례대로 삽입합니다.
2. 다음으로, K번 큐의 첫 번째 원소를 큐의 마지막 위치로 재배치합니다.
3. 그리고, q.front()를 통해 큐의 첫 번째 원소를 출력합니다.

 

#3. 코드

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

int main()
{
    int N, K;
    cin >> N >> K;

    queue<int> q;
    for(int i = 1; i <= N; i++)
    {
        q.push(i);
    }

    cout << '<';
    while(!q.empty())
    {
        for (int i = 0; i < K - 1; i++) {
            q.push(q.front());
            q.pop();
        }

        cout << q.front();
        q.pop();

        if(!q.empty())
        {
            cout << ", ";
        }
    }

    cout << '>';

    return 0;
}