백준 1158번, 11866번 요세푸스 문제 [C/C++]

1158번: 요세푸스 문제

요세푸스 순열

n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다.

 

예를 들어 문제 입력에 10, 7이 주어지면  <7, 4, 2, 1, 3, 6, 10, 5, 8, 9> 처럼 답이 나온다.

 

 

n:10 k:7이 대입된 요세푸스 순열 풀이 과정.

이것을 이해를 돕기위해 적어보았는데 오히려 직관성이 조금 떨어진다..

 

어쨌든 요약하자면 사람의 수가 총 5명이 남았는데 7번째 사람을 죽여야 하는 경우라면 

위 그림처럼 이루어진다.

 

풀이코드

코드1

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
	int n, k;
	int count = 0;
	queue<int> q;
	vector<int> vec;
	scanf("%d %d", &n, &k);

	for (int i = 1; i < n + 1; i++) {
		q.push(i);
	}
    
    //q.size가 0(false)이 되면 while 탈출. 즉 큐가 빌 때까지 계속 반복한다.
	while (q.size()) {
		if (k - 1 == count) {
			vec.push_back(q.front());
			q.pop();
			count = 0;
		}

		else {
			int temp = q.front();
			q.pop();
			q.push(temp);
			count++;
		}
	}

	//출력
	printf("<");
	for (int i = 0; i < vec.size(); i++) {
		if (i == vec.size() - 1) {
			printf("%d>", vec[i]);
		}
		else printf("%d, ", vec[i]);

	}

	return 0;
}

 

코드2

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
	int n, k;
	int count = 0;
	queue<int> q;
	scanf("%d %d", &n, &k);

	for (int i = 1; i < n+1; i++) {
		q.push(i);
	}

	int qsize = q.size();
	//조건문에서 계속 q.size()를 호출해서 크기를 확인하는 것 보다 변수를 놓고 사용.
	printf("<");
	while (qsize--) {
		for (int i = 0; i < k-1; i++) {
			q.push(q.front());
			q.pop();
		}

		if (qsize > 0) {
			printf("%d, ", q.front());
			q.pop();
		}

		else {
			printf("%d>", q.front());
			q.pop();
		}
	}

	return 0;
}

 

코드2처럼 문제를 풀 때 while에 qsize-- 때문에 조건이 헷갈렸었다.

qsize--는 while문 내부로 들어온 뒤 qsize가 감소하기 때문에 최종적으로 qsize가 0일 때도 반복문이 수행된다.

 

그러나 --qsize로 while문의 조건을 설정하면

위와 같이 qsize가 먼저 감소되기 때문에 반복문 수행횟수에 차이가 나게 된다.