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

https://www.acmicpc.net/problem/1158

문제

알고리즘 접근 방법

원형 링크드리스트로 풀다가 오류나서
머리 터질뻔했다..
큐를 이용하면 쉽게 풀 수 있다..!

K번째 사람이 올 때 까지
push & pop 을 반복하면서
동그라미 형태로 뒤로 계속 보내고
차례가 되어 제거할 때는 pop을 이용하여 제거한다.

처음과 끝에 <>을 붙여야 하므로
마지막은 따로 출력해준다.

풀이

#include <iostream>
#include <queue>

using namespace std;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, K, temp;
    
    cin >> N >> K;

    queue<int> q;

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

    cout << '<';

    while(q.size() > 1){
        for(int i=1; i<K; i++){
            temp = q.front();
            q.push(temp);
            q.pop();
        }

        temp = q.front();
        cout << temp << ", " ;
        q.pop();
    }
    
    temp = q.front();
    cout << temp << ">\n";
    return 0;
}

정리

ㅠㅠ 삽질했다.. 큐도 있었지 ..

💡 참고 포스팅

재츠비님 블로그