[baekjoon] 1158번 : 요세푸스 문제 (C++)

처음 이 문제를 보고 생각난 것은 .. 원형 큐였다 그래서 구현하려고 생각해보았으나.. 사람들이 제거될때마다 빈 공간을 땡겨서 내려와야 하고?... 좀 까다로웠다는 것을 깨달아서 다른 방법을 찾았다

 

바로 C++의 SLT중 하나인 Queue를 이용하는 것

k번째 사람이 제거될 때는 pop을 하면 되지만 그렇지 않을 경우에는 맨 앞 원소(front)를 큐에 push한 뒤 pop을 하는 방법으로 큐가 empty가 될 때까지 반복하는 방법이다

 

// BOJ 1158번 : 요세푸스 문제
#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, k; // n: 사람 수 / k: k번째 사람 제거
    cin >> n >> k;
    queue <int> q; // q 생성
    int count = 1; // 전체 숫자 세는 변수
    int result = 1; // 순열 출력이 얼마나 되었는지 측정 변수

    for(int i = 1; i <= n; i++){
        q.push(i); // 큐에 순서대로 숫자 저장
    }

    cout << "<";
    while(q.size()){ // 큐에 원소가 존재할 때
        if(count % k == 0){ // 숫자 출력 (k번째)
            if(result == n){ // 만약 출력 마지막 원소라면
                cout << q.front() << ">"; // 출력하고 닫아줌
                break; // 반복문 종료
            }
            cout << q.front() << ", "; // 원소 출력해 줌
            q.pop(); // 출력한 원소는 제거
            result++; // 출력했으므로 result 증가
        }
        else{ // 출력할 때가 아니라면
            q.push(q.front()); // 맨 앞 원소를 다시 뒤에 추가
            q.pop(); // 뒤에 추가했으므로 맨 앞 원소 제거
        }
        count++; // count 변수 증가
    }
}

맨 끝 '>' 닫는 과정에서 어떻게 처리할까 고민하다가 result 변수를 추가해서 처리해주었다