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

Approach

출처: https://www.acmicpc.net/problem/11866

 

[BOJ 1158 요세푸스] 문제 보다 조건이 더 쉬워진 버전이다.

ex) 메모리 제한, N의 최대값 등

[BOJ] 백준 1158 요세푸스 문제

 

[큐] Queue를 이용하면 쉽게 풀 수 있는 문제이다.

알고리즘 공부하는 사람들에게 요세푸스 문제가

Queue 자료구조를 연습하기 좋은 유형이기도 하다.

[큐] Queue란?

 

K번째에 해당하는 원소까지 pop가 push 동작을 해준다.

FIFO 구조를 이용하는 것이다.

 

<7, 3>에 대한 로직은 아래와 같다.

1 2 3 4 5 6 7 → "3" 제외

4 5 6 7 1 2 → "6" 제외

7 1 2 4 5 → "2" 제외

4 5 7 1 →  "7" 제외

1 4 5 → "5" 제외

1 4 → "1" 제외

4 → "4" 제외

 

제외된 순서과 결과와 동일하다.

(문제에서 요구하는 형태에 맞춰 출력한다.)

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

 

비슷한 유형으로 [Jungol 3101 요세푸스 문제 1]도 있다.

---

 

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

int N, K;
queue<int> que;

void foo()
{
	while (!que.empty())
	{
		for (int i = 0; i < K - 1; i++)
		{
			que.push(que.front());
			que.pop();
		}

		cout << que.front();
		que.pop();

		// 원소가 아직 존재하는 경우
		if (!que.empty())
		{
			cout << ", ";
		}
	}
}

int main()
{
	// freopen("input.txt", "r", stdin);
	cin >> N >> K;

	for (int i=1; i<=N; i++) 
	{
		que.push(i);
	}

	cout << "<";
	foo();
	cout << ">" << endl;
}

 

Java

import java.util.Scanner;

class Queue {
	int front, rear;
	int[] queue;

	public Queue(int size) {
		front = 0;
		rear = 0;
		queue = new int[size];
	}

	public void push(int value) {
		queue[rear++] = value;
	}

	public int pop(int idx) {
		int return_value = queue[idx];
		re_array(idx);
		return return_value;
	}

	public void re_array(int idx) {
		rear--;
		for (int i = idx; i < rear; i++) {
			queue[i] = queue[i + 1];
		}
		return;
	}

	public int find_idx(int m, int idx) {
		idx = idx + m - 1;
		if (idx >= rear) {
			idx = idx % rear;
		}
		return idx;
	}

	public void print_queue() {
		System.out.print("<");
		for (int i = front; i < rear; i++) {
			if (i == rear - 1) {
				System.out.print(queue[i]);
			}
			else {
				System.out.print(queue[i] + ", ");
			}
		}
		System.out.println(">");
	}
}

public class Main 
{
	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();

		Queue item_Q = new Queue(n);

		// n 개의 값을 큐에 삽입
		for (int i = 0; i < n; i++) 
		{
			item_Q.push(i + 1);
		}

		// 입력 받은 m 에 대해 주어진 순열 구현
		Queue result_Q = new Queue(n);
		
		// 입력 받은 갯수 만큼 출력
		int idx = 0;
		for (int i = 0; i < n; i++) 
		{ 
			idx = item_Q.find_idx(m, idx);
			result_Q.push(item_Q.pop(idx));
		}

		result_Q.print_queue();
	}
}