백준 11866번 - 요세푸스 0 문제 C++ [Queue]

📍 백준 11866번 - 요세푸스 0 문제 C++ [Queue]

---

🧩문제 요약

<Queue>

요세푸스 순열 문제를 해결하라. 

요세푸스 순열이란?

출처 : https://siku314.tistory.com/86

---

🧾내가 작성한 초기 코드 

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

int main(){
    int n,k, i, tmp;
    queue<int> q;  
    cin >> n>> k ;
    for(i=1; i<n+1 ; i++){
        q.push(i);
    }
    cout << "<";
    while(1){
        for(i = 1; i<=k; i++){
            if(i!=k){
                tmp = q.front();
                q.push(tmp);
            }else{
                cout << q.front() ; 
            }
            q.pop();
        }
        if(q.size()==1){
            cout <<", " << q.front() << ">\n";
            break; 
        }else{
            cout << ", ";
        }
    }
    return 0; 
}

---

👍이 문제에서 배운점

문제를 잘 풀었다고 생각했느데 자꾸 마지막 97%에서 틀려버려서 뭐가 문제인지 한참을 들여다 봤다. 

😕 문제점 1. 

조건 검사 타이밍의 문제. 

이 문제는 조건 검사 타이밍이 문제였다. 

if(q.size()==1)판단을 for루프 바깥에서 하고 있는데, for루프 안에서 이미pop을 진행하면 q.size()가 줄어들게 된다. 

특히 마지막 2개의 원소가 남았을 때,

예를 들어 q.size()==2 일때, for루프에서 2번 pop이 되면서 큐가 비게 된다. 그래서 마지막 출력전에 q.size()==1 체크를 하지만 이미 큐에서 pop된 상태라 잘못된 결과가 나온다. 

 

즉, 출력이 진행된 후 size를 확인하는데 이미 pop이 일어나서 큐의 크기가 줄어든 뒤라 오작동이 나는 것이다. 

 

✅ if(q.size() == 1) 체크를 for 루프 안쪽으로 옮기거나, pop 전에 크기를 체크해서 마지막 원소일 때 출력 형태를 다르게 하면 된다. 

 

 

---

🧾 완성된 코드 

for(i = 1; i <= k; i++){
    if(i != k){
        q.push(q.front());
    } else {
        if(q.size() == 1){
            cout << q.front() << ">\n";
        } else {
            cout << q.front() << ", ";
        }
    }
    q.pop();
}
if(q.empty()) break;

 

다른 예시  

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

int main(){
    int n,k, i, tmp;
    queue<int> q;  
    cin >> n>> k ;
    for(i=1; i<=n ; i++){
        q.push(i);
    }
    cout << "<";
    while(q.size()!=0){
        for(i = 1; i<k; i++){
                q.push(q.front());
                q.pop();
        }
        cout << q.front() ;
        if(q.size()!=1){
            cout <<", " ;
        }
        q.pop();
    }
    cout << ">\n";
    return 0; 
}

 

---

 

요세푸스 순열이란것을 알게되었다. 처음 보는 수열이였는데 큐를 사용하지 그렇게 어렵지 않게 구현할 수 있었다. 

큐도 그렇고 스택도 그렇고 배열 등 다양한 자료구조를 알고 있으니 확실히 문제 푸는게 쉬워지기도 하는것 같다.