(c++)백준 1158번: 요세푸스 문제

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

1158번: 요세푸스 문제

[풀이]

링크드 리스트로 풀었다.

자기 자신의 번호와 다음 사람의 주소로 이루어진 구조체 배열을 만들어 현재 사람에서부터 K번째에 있는 사람을 찾아다니며 제거해주었다.

 

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

struct Person {
	int Num;//자기 번호
	Person *next;//다음 사람 번호
};

Person P[5001];
vector<int>Remove;//원에서 제거되는 순서
Person *nowP;//현재 위치
int N, K;

//원 이어주기
void makeCircle() {
	for (int i = 0; i < N; i++) {
		P[i].Num = i;
		P[i].next = P + i + 1;
	}
	P[N].Num = N;
	P[N].next = P+1;
	nowP = P;
}

//K번째 사람 찾아서 제거
void findK() {
	Person *p;//이전 사람이 누구인지 저장
	for (int i = 1; i <= K; i++) {
		p = nowP;
		nowP = nowP->next;
	}
	//K번째 사람 제거
	p->next = nowP->next;
	Remove.push_back(nowP->Num);
	nowP = p;
}

void solution() {
	cin >> N >> K;
	makeCircle();//원 이어주기
	
	int Cnt = N;
	while (Cnt--) {
		findK();//K번째 사람 제거
	}

	cout << '<';
	for (int i = 0; i < N - 1; i++) {
		cout << Remove[i] << ", ";
	}
	cout << Remove[N - 1] << '>';
}

int main() {
	solution();
	return 0;
}