백준 11866 요세푸스 문제 0 C++

 

 

예제 입력 1 복사

7 3

예제 출력 1 복사

<3, 6, 2, 7, 5, 1, 4>

 

 

=> 자료구조 queue 를 안다면 구현할 수 있는 문제입니다. 

=> 삭제하고픈 원소를 찾을때까지 이전에 있는 원소들을 큐의 뒤쪽에 삽입합니다. 

=> 삭제하고픈 원소를 찾을 경우, 해당원소를 PRINT하고 POP을 해줍니다. 

=> 요세푸스 QUEUE에 원소가 없을때까지 위의 작업을 반복합니다. 

=> 프린트문 시작 '<'과 프린트문 종료'>' 를 적절한 곳에 넣어줍니다. 

=> 문제풀이는 아래의 그림과 같습니다. 

 

 

문제풀이

 

#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <queue>
#include <utility>
#include <stdio.h>

using namespace std;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N,K;
    cin >> N >> K;
    
    queue<int> jose; //요세푸스 큐
    
    //큐에 원소 삽입
    for(int i=1; i<= N; i++)
    {
        jose.push(i);
    }
    
    //프린트문 시작
    cout << "<";
    
    while(1)
    {
        //k번째 원소가 jose큐 가장 앞에 오도록함
        //나갈원소 앞에 있던 원소들은 jose큐 뒤에 삽입
        for(int i=0; i<K-1; i++)
        {
            int tmp = jose.front();
            jose.push(tmp);
            jose.pop();
        }
        
        cout << jose.front();
        jose.pop();
        //jose 큐가 꽉 찼을 경우, while문 탈출
        if(jose.empty())
        {
            break;
        }
        //jose 큐가 비어있지 않을경우, ','을 찍어줌
        else
        {
            cout <<", ";
        }
    }
    //프린트문 종료
    cout<<">";
}

 

 

2년전에 풀던 풀이방법과 다르게 풀이해보았습니다. 

(2년전 풀이법 : LIST를 사용하여 실제 원소를 삭제하여 구현)