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

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

1158번: 요세푸스 문제

 

어떤 문제인가?

1번부터 N번까지 사람이 있고 K번째 사람을 제거해가며 제거된 사람들을 순서대로 출력하는 문제이다.

 

 

접근 방법

문제에서 사람들이 원을 그리고 앉아있다는 것을 보고 원형 큐를 사용해야겠다고 생각했다.

k번째 사람이 큐의 맨 앞에 오도록 해 준 다음 front를 출력하고 사람이 제거되어야 하니 pop을 해줘야겠다고 생각했다.

 

 

int n, k;
queue<int> q;

cin >> n >> k;

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

 

간단하다. 문제에서 요구한 변수들을 선언하고 입력받는다.

그리고 queue에는 1부터 N까지 추가해준다.

 

 

cout << "<";

while (!q.empty()) {
    for (int i = 0; i < k - 1; i++) {
        q.push(q.front());
        q.pop();
    }

    cout << q.front();
    q.pop();

    if (!q.empty()) {
        cout << ", ";
    }
}

cout << ">";

문제의 출력 조건에 맞춰 '<'를 먼저 출력해주고 반복문을 시작한다.

 

for문은 k번째 숫자를 queue의 맨 앞으로 오도록 해주는 반복문이다.

1 2 3 4 5 6

 

1 push

 

1 2 3 4 5 6 1

 

pop

 

2 3 4 5 6 1

이렇게 보면 쉽게 이해가 될 것이다.

문제의 예시 입력을 받았을 때 반목문을 반복하면 

2 3 4 5 6 1

3 4 5 6 1 2

순서로 3번째인 3이 queue의 맨 앞에 오게 된다.

이제 front를 출력하고 pop해준다.

 

출력 조건에 맞게 숫자 뒤에 queue가 비어있지 않으면 ", "를 붙여 출력해준다.

 

이 반복을 queue가 빌 때까지 반복해주고 ">"로 출력을 마치면 끝!

 

 

무엇이 어려웠는가?

문제를 읽고 바로 원형 큐를 사용해야겠다고 떠올랐다.

원형 큐의 개념만 알고 있었다면 어려움없이 풀 수 있는 문제였다.

 

 

시간 복잡도

큐가 빌 때까지 연산을 while문을 반복한다.

큐의 크기는 입력 받은 n이다.

while문 안 for문 안의 연산은 O(1)이므로 시간 복잡도에 영향이 없다.

 

따라서 시간복잡도는 O(n)이 된다.

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%8D%B8%EB%A8%B8%EC%BD%94%EB%94%A9/1158.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.