[백준 1158] 요세푸스 문제, C++

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

1158번: 요세푸스 문제

 본 문제는 배열을 이용해서 풀 수 있다. 이 문제에서 queue를 사용하는 것이 효율적이지 못하지만 처음에 딱 떠오르는 게 queue였다. 문제를 풀는 것에서 끝내는 게 아니라 좀 더 효율적인 코드를 보면서 공부하는 것이 바람직하다고 생각한다.

1. 순서에 맞는 숫자 찾기
2. 출력 후 지우기

queue 소스코드

#include <cstdio>
#include <queue>
 
using namespace std;
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
 
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }
 
    printf("<");
    while (!q.empty()) {
        for (int i = 0; i < k-1; i++) {
            q.push(q.front());
            q.pop();
        }
        if (q.size() == 1) {
            printf("%d>", q.front());
            q.pop();
        }
        else {
            printf("%d, ", q.front());
            q.pop();
        }
    }
    return 0;
}

 

배열을 사용한 소스코드

#include <cstdio>
 
using namespace std;
 
int main() {
    int d[5001];
    int n, k;
    int now = 0;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        d[i] = i;
    }
    printf("<");
    while (n > 0) {
        now = (now+k) % n;
        if (now == 0) now = n;
        if (n == 1) {
            printf("%d>", d[1]);
        }
        else {
            printf("%d, ", d[now]);
            for (int i = now; i < n; i++) {
                d[i] = d[i+1];
            }
            now -= 1; // 숫자를 제거했으므로 한 칸 뒤로 이동해야 한다.
        }
        n -= 1;
    }
    return 0;
}