백준 11866번 (요세푸스 문제 0) c++

문제

 

문제 풀이

1. 큐를 이용한다.

 

큐는 FIFO(First In First Out)으로 선입선출 즉, 먼저 들어온 얘를 먼저 빼주는 방식이다.

그래서 Enqueue를 하면 맨 뒤에 들어가고 Dequeue를 하면 맨 앞 원소가 나오게 된다.

문제에서 N은 1000개이다. 그래서 그냥 선형 queue를 구현하여 사이즈를 잘못 잡으면 못 맞출 가능성이 있다.

 

이럴 때는 원형 queue를 쓴다면 메모리를 훨씬 절약하여 풀 수 있다.

 

선형 queue는 포화 상태가 아니여도 만약 큐의 rear가 배열의 마지막 인덱스와 같다면 포화 상태로 인식하여 더 이상 삽입 할 수 없다.

하지만 원형 queue는 선형 queue와 다르게 만약 큐의 rear가 배열의 마지막 인덱스이면서 포화 상태가 아니라면 rear를 queue의 비어있는 앞으로 보내주어 계속 삽입을 할 수 있게끔 만들어 준다.

 

 

문제에서 N개 중 K번째 수를 차례대로 빼주면 된다. 그렇다면 먼저 queue에 N개의 숫자를 넣은 뒤, K번째일 때 Dequeue를 하고 K번째가 아닐 때 Dequeue를 똑같이 해주지만 그 Dequeue한 값을 다시 queue에 Enqueue를 하면 된다.

 

전체 코드

 

#include <iostream>

using namespace std;

int queue1[1000001] = {0,};
int result[1000001] = {0,};

int start1 = 0;
int end1 = 0;

void push(int in){

        queue1[end1] = in;
        end1++;
        end1 %= 1000001;

}

int pop(){

        int ans = queue1[start1];
        start1++;
        start1 %= 1000001;
        return ans;

}

int main(){

        int N;
        int K;

        cin >> N >> K;

        for(register int i = 0; i < N; i++){

                queue1[i] = i+1;

        }

        end1 = N;

        int count = 1;

        int temp = 1;

        while(count < N+1){

                if(temp == K){
                        result[count++] = pop();
                        temp = 1;
                }
                else{
                        push(pop());
                        temp++;
                }

        }

        cout << '<';
        for(register int i = 1; i < N; i++){
                cout << result[i] << ", ";
        }
        cout << result[N] << '>' << '\n';

        return 0;

}