[ C++ ] #1158 요세푸스 문제

이 문제는 자료구조를 잘 이용하는 문제인것 같다는 생각이 든다.

정해진 만큼 이동하고 출력하고 삭제하고, 마지막을 만나면 다시 처음으로가고 하면될 것 같다.

 

알고리즘은 별로 안어려운데 자료구조를 잘 활용해야할 것 같다. 

 

list도 이용해봤고 vector도 이용해봤는데 동적으로 계속 사이즈가 변해서

코드를 작성하기 힘들었다.

 

그래서 배열을 이용해서 해결하였다. 

사용완료된 배열에는 숫자대신 -1를 넣어줌으로써 k를 셀때 제외할 수 있도록 하였다.

현재 인덱스 번호가 배열사이즈를 넘는다면 다시 처음으로 돌아가도록 하였다. 

 

#include <iostream>


using namespace std;

int main() {

	int a;
	cin >> a;
	
	int* p = new int[a];  //동적할당
	for (int i = 0; i < a; i++) {
		p[i] = i + 1;
	}
	int b;
	cin >> b;

	//출력
	cout << "<";
	int index = -1;
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			index++;
			if (index == a)index = 0;  //배열크기 넘어갈시 맨 앞으로 이동
			if (p[index] == -1)j--;  //사용완료된 배열 세지 않기
		}
		if (i == a - 1) {
			break;
		}cout << p[index] << ", "; p[index] = -1;  //배열값 출력 후 -1로 사용완료 표시
	}

	cout << p[index] << ">";


}

 

글을 찾아본 사람 중 나처럼 푼 사람은 없었다.

그래서 STL 공부겸 다른 코드를 가져와서 분석해보겠다.

 

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


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

	//입력
	int n,k;
	cin >> n>>k;
	
	queue<int>q;
	for (int i = 1; i <= n; i++)q.push(i);

	cout << "<";

	//문제 해결
	while (q.size() > 1) {
		for (int i = 1; i < k; i++) {  //k번 반복
			int tmp = q.front();
			q.pop(); //앞에서 빼서
			q.push(tmp); //뒤에 다시 넣는다
		}
		cout << q.front() << ", ";
		q.pop();
	}
	cout << q.front() << ">\n";
}

이 코드는 출력해야하는 숫자 앞 숫자들은 뒤에 줄세우고

앞에 숫자는 출력후 삭제해주는 알고리즘이다.