[BOJ] 1158번 요세푸스 문제

요세푸스 문제 << 클릭!

---

✅문제 설명

• N (1<=N<=5000) : 사람 수, 원을 이루며 순열
• 양의 정수 K(<= N) : 제거할 사람 번수

• K번째 사람이 제거 그 후 남은 사람들도 이루어진 원을 따라 반복
• 이때 K번째 사람의 다음 번째가 1번임
• 예를 들어 N=7 K=3이라고 할 때 처음에 3번이 제거, 그 다음에 6번이 제거(4번-1번으로 update, 5번-2번으로 update, 6번- 3번으로 update)

❗핵심원리

• 문제 속 '원'에 집중해보자
  번호가 있음에도 원으로 앉아 있기 때문에 시작과 끝이 제거될 때마다 바뀐다.
  K번째 다음 번째가 다음 원의 시작이다.
  사람 명수가 K 이하인 경우에는 주어진 사람 번수에서 k번째가 될 때까지 순환한다.

  ✅ 큐와 같은 자료구조를 이용
  

💻코드

#include <iostream>
#include <vector>

using namespace std;

int main(void) {
	int n;
	int k;
	cin >> n >> k;

	vector<int> v;


	for (int i = 0; i < n; i++) {
		v.push_back(i+1); // 벡터에 N번까지 추가
	}

	int idx = k - 1; // 0번이 1번이기 때문에 k번은 k-1번

	cout << "<";
	for (int i = 0; i < n; i++) {
		if (i == n - 1) { // i가 끝이면 
			cout << v[idx] << ">"; 
			break;
		}
        
        	// i가 끝이 아닌 경우
		cout << v[idx] << ", ";
		v[idx] = 0; // 이미 담김
		int count = 0; //초기화 


		while (count != k) { // count가 k일때까지 idx를 1씩 늘림  
			idx  = idx + 1; // 해당 인덱스+1 

			if (idx > n - 1) { // n-1보다 크다면 빼주기
				idx = idx - n;
			}

			if (v[idx] != 0) { // 해당 인덱스가 0이 아니라면 1을 더해줌
				count = count + 1; 
			}
		}
	}

}

• 즉 K번동안 idx가 움직이는 것을 N번 반복하기 때문에 시간복잡도는 O(KN)

다른 분들의 풀이 (출처:https://hyeonnii.tistory.com/156 [From the bottom])

#include <iostream>
#include <queue> // 중요 
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false); 
    int N, M;
    queue<int> q;
 
    cin >> N >> M; 
 
    //initial queue
    for (int i = 1; i <= N; i++)
        q.push(i);
 
    //operation and print
    cout << "<";
    while (q.size()) {
        if (q.size() == 1) //the last one
        {
            cout << q.front() << ">";
            q.pop();
            break;
        }
        for (int i = 1; i < M; i++) { // M번 반복 
            q.push(q.front()); // 맨 앞의 원소를 맨 뒤에 추가.  
            q.pop(); // 맨 앞 원소를 삭제 
        }
        cout << q.front() << ", "; 
        q.pop();
    }
    cout << endl;
    return 0;
}

• 대부분 queue를 이용한 풀이를 볼 수 있었다.

• 나의 풀이와 거의 비슷하지만 다른 점은 나는 인덱스를 이동시켰고 위의 풀이는 원소를 직접 이동시켰다는 점이다.

  
  
  

  큐 말고 원형 큐를 이용한 방법도 있으니 참고만 하기로 하자!