[BOJ] 백준 11866번: 요세푸스 문제 0 (C++)

 

 

- 문제 출처 : https://www.acmicpc.net/problem/11866

---

1. 생각

이번에는 요세푸스 문제를 들고 왔다.

원을 이루고 앉아있는 N명의 사람들을 주어진 K번째 사람을 연속해서 제거해 모두 제거될 때까지 반복하는 문제다.

 

처음에는 원을 이루고 앉아있다고 해서 뭐 환형 큐? 이런건가 싶었는데,

그렇게 어렵게 생각할 것 없이, 현재 차례 사람(front) 이 K번째에 해당 되지 않으면

후순위 (back)로 보내면 될 것으로 보였다.

 

따라서, 한쪽 방향에서만 자료가 pop되고, push 된 순서대로 pop 되므로, 큐를 쓰는 문제임을 파악할 수 있다.

그리하여 이전 문제들과 마찬가지로 C++의 STL에 있는 queue를 활용하여 문제를 풀어보았다.

 

2. 난관 & 해결 방법

 for (int i = 1; i <= n; i ++)
    q.push(i);

 

N만큼의 사람을 우선 queue에 넣어주었다.

이전 문제에서는 i + 1 을 push 하였지만, 조금 더 직관적으로 push 하기 위해

for문의 인덱스 자체를 1부터 시작하도록 바꾸었다.

 

std::cout << "<";
while (!q.empty())
{
    for (int i = 0; i < k - 1; i ++)
    {
        q.push(q.front());
        q.pop();
    }
    std::cout << q.front();
    q.pop();
    if (!q.empty())
        std::cout << ", ";
}
std::cout << ">\n";

 

생각했던 것처럼 k번째 사람이 나오기 전까지는 현재 front에 있는 자료를 그대로 push하고 pop해줬다.

그러면 후순위로 해당 자료가 밀린 것과 동일하게 동작하였다.

 

그 이후는 이제 우리가 원하는 k번째 데이터가 나오고, 해당 데이터를 출력한 뒤 pop했다.

그 후에는 비어있지 않으면 쉼표를 작성한 뒤 while문을 다시 동작시켜 다음 k번째 자료가 나오도록 했다.

 

이 과정을 모두 반복한 뒤 while문을 탈출하면 로직이 완성된다.

 

3. 코드 및 결론

[ 전체 코드 ]

#include <iostream>
#include <queue>

int main(void){
    std::queue <int> q;
    int n, k;
    std::cin >> n >> k;
    
    for (int i = 1; i <= n; i ++)
        q.push(i);
    std::cout << "<";
    while (!q.empty())
    {
        for (int i = 0; i < k - 1; i ++)
        {
            q.push(q.front());
            q.pop();
        }
        std::cout << q.front();
        q.pop();
        if (!q.empty())
            std::cout << ", ";
    }
    std::cout << ">\n";
}

 

[ 결론 ]

 

처음에 수열을 보고는 이걸 어떻게 해석해야할지 난감했지만,

시뮬레이션을 해보니 정말 단순한 문제였고 해결 방법도 상당히 간단했다.

이런 구현문제들을 해보면서 점차 프로그래밍적 사고를 할 수 있을 것 같아서 재미있게 느껴진다.

 

점차 쌓여가는 자료구조 활용방법들을 토대로 추후에 제대로 구현문제를 풀어보고 싶다!