[Baekjoon] 11866: 요세푸스 문제 0 - (C2, S4) std::vector

 

문제
요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력
예제와 같이 요세푸스 순열을 출력한다.

11866번: 요세푸스 문제 0

 

요세푸스 문제를 보자마자 떠오른 알고리즘은 다음과 같다. 

• 1. 가변 크기의 배열, 혹은 리스트를 사용한다. (본인은 vector을 사용하였으므로, 이하 vector라 칭한다.)
• vector의 크기에 따라 삭제할 인덱스를 mod 연산하면 하나의 반복문으로 해결할 수 있을 것이다. 

예제인 (7, 3)-요세푸스 순열은 다음과 같다. 

 

• 1. vector 생성 1 2 3 4 5 6 7 (N=7, K=3)
  • 초기 제거 인덱스: idx = K - 1 (idx = 2, 3 제거)
  • 결과: 1 2 4 5 6 7 (size: 6)
• 2. 6 제거 , idx = (1 + 3) % 6 = 4
  • 결과: 1 2 4 5 7 (size: 5)
• 3. 2 제거, idx = (3 + 3) % 5 = 1
  • 결과: 1 4 5 7 (size: 4)
• 4. 7 제거, index = (0 + 3) % 4 = 3
  • 결과: 1 4 5 (size: 3)

이와 같은 과정을 반복해 <3, 6, 2, 7, 5, 1, 4>를 얻는다. 위에서 초기 제거 인덱스를 제외하면, 모두 idx = (idx - 1 + K) % size로 갱신되는 것을 확인할 수 있다. 그렇다면 어떤 자료구조를 써야하는지가 문제인데, 이미 위에서 언급한 바와 같이 vector 컨테이너를 사용하였다. 

 

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

int main()
{
    int N, K;
    cin >> N >> K;

    vector<int> josephus;
    josephus.reserve(N); 

    for (int i = 0; i < N; i++)
        josephus.push_back(i + 1);

    int idx = K - 1;
    cout << '<' << josephus[idx];
    josephus.erase(josephus.begin() + idx);

    for (int i = 0; i < N - 1; i++)
    {
        idx = (idx - 1 + K) % josephus.size();
        cout << ", " << josephus[idx];
        josephus.erase(josephus.begin() + idx);
    }
    cout << '>';

    return 0;
}

std::vector는 템플릿으로 구현된 동적 배열 컨테이너이다. list에 비해 임의의 요소에 접근이 간편하고 빠르기 때문에 선택하였다. 

vector 선언 후, reserve 함수를 이용해 미리 N개의 데이터를 저장할 메모리를 할당한다. 

 

그리고 push_back 함수를 반복하여 초기 배열을 생성한 후, 1번째 제거를 수행한다. 

 

이후 for문을 이용해 idx를 갱신하며 순열을 완성한다. 

 

깔끔하게 한번에 마무리.