[백준 11866번] 요세푸스 문제 0

나의 첫 접근

이미지 첨부 바람

스택으로는 일일이 접근 못 하니 앞에 있는 것을 뒤로 추가해준다. 이거는 몇 달 전에 본 사고 방식 같다.

 

vector로 풀다 문제 의도를 너무 벗어난 것 같았다.

다른 사람 풀이 참고

K번째 사람--이거는 순서 관련 변수 하나를 정해서 이게 K로 나눠떨어지나 아닌가를 판별하고

K의 배수가 아니면 앞에 원소를 뒤로 추가해준다.

int x = Q.front();
Q.pop(); // 뺄 때는 앞이 빠지고
Q.push(x); // 추가해줄 때는 뒤로 추가가 된다.

 

나는 무작정 K-1번 for문 돌리고 pop 하였는데

그것보다 K로 나눠떨어지는지 확인해주고 조건 처리해주는게 좀 더 깔끔해보인다.

 

최종 정답 코드

풀이방법 : 

 1. 사람을 모두 제거할 때까지 loop를 돕니다.

 2-1. 일정 순번(k)째가 되면 그때 queue를 pop한 후 출력합니다.

 2-2. 일정 순번째가 아니면 queue의 가장 앞 원소를 가장 뒤쪽으로 옮겨줍니다.

 3. < > 과 ,를 잘 출력해주도록 조절해줍니다.

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

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	queue<int> Q;
	int N;
	int K;
	cin >> N >> K;
	
	int removedPerson = 0;
	int cur = 1; // 순서
	for (int i = 1; i <= N; i++)
	{
		Q.push(i);
	}
	cout << "<";
	while (removedPerson != N) {
		while (1) {
			if (cur++ % K == 0) {
				cout << Q.front(); // 조만간 빼낼 애
				Q.pop();
				removedPerson++;
				break;
			}
			else {
				Q.push(Q.front());
				Q.pop();
			}
		}
		if (removedPerson != N)cout << ", ";
	}
	cout << ">";
	return 0;
}

break문을 써서 안에 꺼 생략해준다는데... break문 쓰는게 익숙치 않다.

+)순서가 K의 배수가 되면 지워준다.

+)지워진 사람의 수에 관한 변수 removedPerson와 지금 순서에 관한 변수 current도 추가해줬다. 사이즈가 1인가로 판별하는 것보다는 지워진 사람이 N이 되기 전까지(removedPerson!=N) 이게 더 명확한 거 같다.

출처)https://codecollector.tistory.com/660

 

break문을 안 쓰고 해보자. 근데... empty 확인 필요

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

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	queue<int> Q;
	int N;
	int K;
	cin >> N >> K;

	int removedPerson = 0;
	int cur = 1; // 순서
	for (int i = 1; i <= N; i++)
	{
		Q.push(i);
	}
	cout << "<";
	while (removedPerson != N) {
		while (!Q.empty()) {
			if (cur % K == 0) {
				cout << Q.front(); // 조만간 빼낼 애
				Q.pop();
				removedPerson++;
				if (removedPerson != N)cout << ", ";
			}
			else {
				Q.push(Q.front());
				Q.pop();
			}
			cur++;
		}
		
	}
	cout << ">";
	return 0;
}

 

요세푸스 문제 1158번) N과 K의 크기만 좀 달라지고 나머지는 다를 바 없는 듯- stl 안 쓰면 N과 K를 5000으로 할당해줘야지. 크기가 5000인 배열이나 리스트처럼.

 

문제 유형 분석

스택, 큐 문제에서는 push, pop을 자유자재로 하는게 중요하고

어떤 상황에서 어떻게 조건 처리를 해서 push하고 어떤 인덱스 늘려주고 이게 중요한듯 하다.

 

오늘 배운 거) 후위 연산자와 break를 이용한 표현 방법 : 내 코드와 비교하면서 복습해본다!