[코딩테스트 / c++] 백준 1158 요세푸스 문제

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

1158번: 요세푸스 문제

요세푸스 유사한 문제를 풀다가 백준에 비슷한 문제가 있어서 연습삼아 풀어보았다. 요세푸스는 조세퍼스라고도 하며 순열을 가리킨다.

 

> 요세푸스 유사문제 포스팅

https://meongj-devlog.tistory.com/201

[코딩테스트 / c++] 공주 구하기 (조세퍼스) 문제

 

 

 

문제

요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력
예제와 같이 요세푸스 순열을 출력한다.

 

예제 입력1

7 3

예제 출력1

<3, 6, 2, 7, 5, 1, 4>

 

 

풀이

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

//백준1158번 - 요세푸스 

int main(){
	
	int n, k;
	
	scanf("%d %d", &n, &k);//n명 k번째 
	
	queue<int> q;
	
	for(int i=1; i<=n; i++)
	    q.push(i);
	
	printf("<");
	
	while(q.size()){
		
		if(q.size()==1){
			printf("%d>", q.front());
			q.pop();
			break;
		}
		
		for(int i=1; i<k; i++){
			q.push(q.front());
			q.pop();
		}
		printf("%d, ", q.front());
		q.pop();
		
	}
	
	
	
	return 0;
}

제외된 사람들을 순열로 출력해야 하기 때문에 배열보다는 queue를 사용하여 구하는 게 적합할꺼 같아 queue로 저장하여 구하였다. 먼저 queue에 1부터 n까지의 숫자를 임의로 넣었다.  

k번째 수만큼 queue 맨앞에 있는 숫자를 뒤로 보내고 k번째가 된 수의 맨앞 숫자를 출력한다. 출력되면 pop해서 내보낸다. 큐의 크기가 1이되면 맨앞 숫자 내보내고 pop해서 끝내면 끝!

 

 

C++의 큐의 기본함수는 다음과 같이 쓸 수 있다.

📌큐 기본함수
#include<queue> 선언

1. 큐에 데이터 넣기
queue.push(데이터)

2. 큐 데이터 삭제(맨 앞)
queue.pop()

3. 큐의 맨 앞 데이터 출력
queue.front()

4. 큐의 마지막 데이터 출력
queue.back()

5. 큐의 사이즈 출력
queue.size()

6. 큐가 비어있는 지 확인
queue.empty()