1158번: 요세푸스 문제

- 문제 사이트: https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

주어진 큐의 원소들을 K - 1번 회전시킨 뒤 맨 앞의 원소 (== K번째 원소)를 출력 및 제거하는 것을 마지막까지 반복해주는 문제이다.

 

1) 큐에 1부터 N까지 수를 저장

2) K - 1번 회전 (맨 앞의 원소를 맨 뒤에 저장 후 맨 앞의 원소 제거)

3) K번째 수 출력 후 제거

4) 큐에 남아있는 원소가 없을 때까지 반복

 

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, K;
    cin >> N >> K;
    queue<int> q;
    for (int i = 0; i < N; i++)
        q.push(i + 1);

    cout << "<";
    while (q.size() > 1)
    {
        for (int i = 0; i < K - 1; i++)
        {
            q.push(q.front());
            q.pop();
        }
        cout << q.front() << ", ";
        q.pop();
    }
    cout << q.front() << ">";
    return 0;
}

- 메모리: 2152 KB

- 시간: 64 ms

- 코드 길이: 524 B

 

굳이 큐를 사용하지 않고 배열로도 문제를 풀어줄 수 있다.

 

1) 1부터 N까지 배열에 저장

2) 출력할 수의 index 설정: idx = K - 1

3) index 위치의 수 출력

4) index 다음 위치의 수들을 한 칸씩 앞으로 당겨옴

5) 전체 배열 크기 1만큼 감소: size -= 1

6) 다음 출력할 수의 index 설정: idx = idx + (K - 1) → 현재 위치를 포함하여 뒤로 K번째 위치

7) 이동한 index 값이 전체 배열 크기보다 큰 경우에 대한 예외 처리 설정: index = index % size

 

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin >> N >> K;

    int nums[N];
    for (int i = 1; i <= N; i++)
        nums[i - 1] = i;

    int size = N;
    int idx = K - 1;
    cout << "<";
    for (int i = 0; size > 1; i++)
    {
        cout << nums[idx] << ", ";
        for (int j = idx; j < size; j++)
            nums[j] = nums[j + 1];
        size--;
        idx += (K - 1);
        if (idx >= size)
            idx %= size;
    }
    cout << nums[0] << ">";
    return 0;
}

- 메모리: 2020 KB

- 시간: 0 ms

- 코드 길이: 590 B