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

🔗알고리즘 문제

처음으로 시간초과라는 문턱에 막혀 시간복잡도에 대해 공부하고 어떻게 해야 더 빠른 로직을 짤 수 있는지에 대해 많이 고민해본 문제이다. 이 때에 경헙을 바탕으로 코드를 짤 때 시간복잡도에 대해 고민하며 짜는 능력을 기른 것 같다.

문제 분석

이 문제는 마치 수건돌리기처럼 N까지의 숫자를 숫자가 모두 없어질 때 까지 K번째 순으로 제거하며 제거 된 순서를 출력하는 문제이다.

예를 들어 N이 7 K가 3이 주어졌다면

1 2 [3] 4 5 6 7
1 2 4 5 [6] 7
1 [2] 4 5 7
1 4 5 [7]
1 4 [5]
[1] 4
[4]

이러한 형식으로 1부터 N까지의 숫자를 K번째 순으로 계속 제거하게 되고 제거 된 순서인 3 6 2 7 5 1 4가 출력되게 된다.

발상

우선 이 문제를 해결하기 위해서 총 세가지 단계를 거쳐야 한다.

1. 숫자가 모두 제거되었는지 계산.
    
2. K번째 숫자가 무엇인지 계산.
    
3. 배열을 넘어가면 처음으로 돌아가기.

숫자가 모두 제거되어 더 이상 제거할 숫자가 없을 때까지 위에 로직을 계속 반복하며 알맞은 숫자를 제거해야한다.

처음에는 이 문제를 배열을 활용하여 풀기로 하였지만 배열에 끝까지 for문, 이미 삭제 된 요소는 넘어가고 K번째 숫자 계산 을 위하여 이중 for문이 필요했고 시간초과를 해결하지 못하였다.

이중 for문을 안쓰고 어떻게 구현할가를 고민하고 있을 때 선생님의 조언을 통하여 원형 큐를 사용할 수 있겠다는 생각을 하였다.

알고리즘 설계

1. N과 K를 입력받는다.
2. 1부터 N까지 for문을 진행하며 queue에 값을 채워넣는다.
3. queue가 모두 빌 때 까지 for문을 진행하며 k번째 수를 찾고 지운다.
   ㄴ 이 과정에서 원형 큐가 구현됨

[원형 큐]

queue의 맨 앞에 값을 맨 뒤로 넣어준 후 
queue를 한번 pop 해줌

코드

#include<iostream>
#include<queue>

using namespace std;

int main(){
    int n, k;
    queue<int> _queue;

    cin >> n >> k;
    cout << "<";

    for(int i = 1; i <= n; i++){
        _queue.push(i);
    }

    for(int i = 1; !_queue.empty(); i++){
        if(i % k == 0){
            if(_queue.size() == 1){
                cout << _queue.front();
            }
            else{
                cout << _queue.front() << ", ";
            }

            _queue.pop();
        }
        else{
            int temp = _queue.front();
            _queue.pop();
            _queue.push(temp);
        }
    }
    cout << ">";
}