[c++]백준1158번:요세푸스 문제

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

1158번: 요세푸스 문제

---

가장먼저 떠오른 방법

:

'꺼내고 뽑고' 라는 키워드에서 큐 문제라는 생각이 직관적으로 들었다.

원형 큐를 직접 c로 구현하여 사용할까 하다가,,, 구현하기 복잡하고 코드가 길어져서 좀 아닌거 같다는 생각이 들었고

 

그 다음으로 가장 먼저 떠오른 방법은 N개의 크기를 가진 1차원 배열 A,B 2개를 사용하는 방법이었다.

배열 A에는 배열값으로 꺼내지지 않은 원소는 1, 꺼내진 원소는 0으로 지정하였고

배열 B에는 배열 A에서 꺼내진 원소 순서대로 차곡차곡 담는 배열이었다.

(배열선언은 크기 N으로 동적할당하여 사용하였다.)

 

요세푸스 배열을 만들때,

하나의 수를 꺼낼 때를 한 번 이라고 한다면

매 번 시작하는 인덱스를 따로 기억해두었다가

다음 요세푸스 배열 만들때 기억해뒀던 인덱스에서 다시 K개씩 세는 방식이었다.

이때 아까 생각났던 원형큐(맨뒤->맨앞 으로 인덱스 이어짐) 개념을 적용하기 위해

인덱스가 N이 넘어가지 않도록 인덱스 = 인덱스%N 처리를 따로 해주었다.

 

뭔가 만들다보니 선언해야하는 변수도 많아지고,

반복문 안의 코드가 직관적이지 않아서

이 방법으로 다 풀고 난 다음에 큐를 이용한 다른 좋은 방법이 없을까 구글링해보기로 생각했다.

 

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);     // 시간초과방지

	int N, K;

	cin >> N >> K;

	int* a = (int*)malloc(N * sizeof(int));

	for (int i = 0; i < N; i++)		// 빼내기전 1 , 빼낸 후 0
		a[i] = 1;

	int *b = (int*)malloc(N * sizeof(int));	// 요세푸스 순열
	
	printf("<");
	int start = 0;
	for (int i = 0; i < N; i++) {		// N번 꺼내기
		int c = 0;
		int j = start;		// 시작지점 인덱스
		while (c != K) {
			j = j % N;		// 배열이 원형으로 작동하기 위함

			if (a[j] == 1)
				c++;		// 요세푸스 순열에 들어갈 K개 세는 과정
			
			j++;		// 인덱스 1씩 증가하며 K개가 될때까지 계속 세어주기
		}
		b[i] = j;		// 요세푸스 순열에 꺼낸 수 순서대로 저장(i=0~N-1)
		a[j - 1] = 0;		// 해당수를 꺼냈음을 표시(1->0) 

		if (j >= N)
			j = j % N;		// 인덱스 에러 방지
		start = j;		// 시작지점인 a의 인덱스(0~N-1) 지정


	}
	
	for (int i = 0; i < N - 1; i++)
		printf("%d, ", b[i]);
	printf("%d>", b[N - 1]);

	return 0;
}

---

다르게 접근해본 방법

:

원형큐 개념을 STL 큐 라이브러리를 사용하여 풀 수 있는 방법이 없을까?

문제에 대한 접근법을 고민하고 구글링해보다가.. 좋은 방법을 알아냈다.

 

바로 큐를 사용하되

k-1번째까지는 pop해서 다시 뒤에 push하고

자동적으로 맨 앞에 오는 k번째 원소를 출력한 뒤 pop해주는 방식이었다. 

 

이렇게 구현한다면 

내가 가장 먼저 떠올렸던 원형 큐를 c로 한땀한땀 구현하지 않고도

비슷한 의도로 접근 할 수 있겠다 라는 생각이 들었다.

 

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);     // 시간초과방지

	int N, K;

	cin >> N >> K;

	queue<int> q;
	
	for (int i = 0; i < N; i++)
		q.push(i + 1);

	cout << "<";

	for (int i = 0; i < N - 1; i++) {		// 맨 마지막 요소의 출력때문에 N-2까지만 반복문에서 출력
		for (int j = 0; j < K - 1; j++) { // K 번째 직전까지의 수들을 맨뒤로 옮기기
			int tmp = q.front();
			q.pop();	// 앞에서 뺀다음
			q.push(tmp);	// 맨 뒤로 옮기기
		}
		cout << q.front() << ", ";	// 요세푸스 순열에 해당하는 수를 출력하고
		q.pop();		// 수열에 넣은 수는 제거
	}
	cout << q.front();
	cout << ">";

	return 0;
}

 

다만, 이 문제 같은경우에는

요세푸스 배열을 출력할때 맨 앞과 맨 뒤에 < , > 를 출력해야하므로

맨 마지막 원소를 따로 출력하고 >로 닫아주기 위해

반복문을 N번이 아닌 N-1번만 작동시켜주었다.

 

---

깨달은 점

:

C++ STL Queue 라이브러리로도 원형큐와 비슷하게 구현할 수 있다.

꺼내고자 하는 원소(k번째)의 이전 원소(1~k-1번째)들을 차례대로 pop해서 다시 push 시켜주면 된다.

 

순서를 유지하면서 특정 맨 앞의 원소를 빼고 싶다면

특정 원소 이전의 원소들을 다시 뒤로 push 시켜주면 된다.