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

 

 

문제 : https://www.acmicpc.net/problem/11866 

 

 

---

 

 

 

 

요세푸스 문제를 풀기 위해서는 기본적인 '요세푸스 순열' 의 개념에 대해 알고 있어야 한다.

 

n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.

출처 : https://ko.wikipedia.org/wiki/%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4_%EB%AC%B8%EC%A0%9C

 

위 개념적인 설명 후에 '(7,3) 요세푸스 순열은 {3,6,2,7,5,1,4}이며 4번째 위치한 사람이 마지막으로 제외되게 된다.'

라는 예시가 나와있다. 위 예시는 백준 문제와 같다.

 

나는 위 예시부터 이해가 되지 않았다. 7개의 수가 있고 3번째 사람부터 제거를 한다는 것 알겠지만

그건 별개로 저 순열은 왜 3,6,2,7,5,1,4 순서가 되는지 이해가 되지 않았다.

 

어떻게 위 문제를 풀 수 있을까? 고민을 많이 해보았다.

 

이제 풀이를 한번 보자.

 

 

풀이

---

1️⃣ 문제 분석하기

일단 원을 한번 그려보았다.

 

일단 순서대로 숫자를 나열하였다. 그리고 요세푸스 순열을 말대로 라면 (7,3) 7개의 숫자중 3번 째 숫자를 제거하는 것 이니 

시작은 1부터 한다고 가정하였을 때 사라지는 숫자는 '3' 이 되어야 할 것이다.

 

그럼 다음 그림을 보자

 

'3' 이 사라졌다. 그리고 사진 왼쪽 하단에 사라진 숫자의 숫자를 담아 두었다.

그리고 '초록색 별' 은 현재 인덱스을 위치를 의미한다. 

즉 3이 사라지고 다음번에 나열된 숫자이다. 3이 사라졌으니 3자리는 당연히 '4' 가 채우게 될 것이다.

 

그리고 다시 세번째 숫자를 없애보자. '4' 기준으로 3번 째는 '6' 이 될 것이다.

 

자 이제 혹시 감이 좀 오나요?

 

다음으로 사라질 숫자는 무엇일까요? 바로 '2' 입니다. 저도 여기 까지 그림으로 그려보았더니 이제야 이해가 되었습니다.

그리고 사라질 숫자는 5, 1, 4 순으로 사라지게 될 것이고 

최종적으로 사라진 숫자를 담은 배열을 보면 

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

 

백준 문제의 출력에 나온 값과 똑같아졌습니다.

 

 

2️⃣ 요구 조건 구현하기

위 문제 분석을 통해 문제를 이해했습니다.

그럼 과연 위 문제를 어떻게 코드에 녹여내야 할까요? 

 

저는 알고리즘 문제를 풀면서 문제는 이해가 되었지만 어떻게 코드에 녹여낼지가 아직은 어렵게 느껴집니다. 

 

위 문제를 풀기 위해서는 Java 의 자료구조를 잘 활용할 수 있어야 합니다.

제가 처음으로 생각난 자료구조는 'ArrayList' 였습니다.

 

ArrayList 자료구조에 순열을 순서대로 담고 remove 메소드를 통해서 문제를 풀 수 있을 것 같다는 생각이 들었습니다.

물론 풀 수는 있을 것 같습니다. 하지만 ArrayList 는 중간에 값을 빼는 것이 좋지 않다?

-> 위 부분 보완하기

 

하지만 위 문제의 핵심은 스택,큐,덱 중 알맞은 자료구조를 사용하여 문제를 푸는 것 이였기 때문에 

List 가 아닌 최대한 스택,큐,덱 중 자료구조를 선택하여 풀수 있습니다.

 

위 문제의 특성을 봤을 때는 스택 자료구조는 아닌 것 같고, 큐 자료구조가 제일 알맞을 것이라고 생각했습니다.

 

이유는 Stack 은 특성상 LIFO 를 가지고 있고, Queue 는 FIFO 를 가지고 있기 때문에

유연하게 데이터가 왔다갔다가 가능한 'Queue' 를 사용하는게 좋다고 판단하였습니다.

 

하지만 문제가 간단하므로 편의를 위해서 'List' 자료구조를 사용하였습니다.

 

최종적인 흐름으로는

0) (N, K) 입력받음

1) Queue 에 N 만큼 순서대로 for 문을 통해 add 를 한다.

2) 그리고 for 문을 통해 queue 에 사이즈 만큼 반복을 돌려 K 번째 숫자를 제거하면서, 제거 된 순서대로 새로운 배열에 담아둔다.

3) 제거 된 값이 담긴 배열을 출력한다.

 

이 정도로 정리가 될 것 같습니다.

 

3️⃣ 슈도 코드

BufferedReader 와 StringTokenizer 를 통해 N,K 를 입력받는다.

	Queue<Integer> queue = new LinkedList<>();
    	for문을 통해 Queue 에 값을 add 한다.
        
    int[] result = new int[queue.size()];
    
    for 문을 통해 K 번째 숫자를 제거한다.
    	제거 된 값을 result 에 추가한다.


	result 출력

 

 

 

4️⃣ 코드 작성

[LinkedList]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class B11866 {
	public static void main (String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		List<Integer> queue = new LinkedList<>();
		for (int i = 0; i < N ; i++) {
			queue.add(i);
		}

		List<Integer> result= new LinkedList<>();
		int idx = 0;
		for (int i = 0; i < N; i++) {
			idx = (idx + K -1) % queue.size();
			result.add(queue.remove(idx) +1);
		}


		System.out.print("<");
		for (int i = 0; i < result.size(); i++) {
			System.out.print(result.get(i));
			if (i < result.size() - 1) System.out.print(", ");
		}
		System.out.print(">");

	}
}

 

 

 

5️⃣ 핵심 파악하기

- Stack, Queue 자료구조의 개념을 알고 있어야 했고, 적절한 자료구조를 사용할 수 있어야 한다.

 

 

결론

알고리즘 문제들은 어렵지만, 해결만 한다면 정말 재밌다.

하지만 해결이 안될 때는 매우매우 화가 난다.