[백준] 11866번 : 요세푸스 문제 0 - JAVA [자바]

 

 
www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

 

 

---

• 문제

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

큐를 이용한 매우 쉬운 문제다.

 

예제를 이해해보자면 이렇다. 1부터 N까지 나열 된 수에서 K번째 수 마다 차례대로 뽑아 낸 수열을 출력하는 것이다.

 

예제를 예로 들어보자.

 

seq {1, 2, 3, 4, 5, 6, 7}, result {}

 

round 1 : seq {1, 2, 3, 4, 5, 6, 7},   result {3}

round 2 : seq {1, 2, 4, 5, 6, 7},   result {3, 6}

round 3 : seq {1, 2, 4, 5, 7},   result {3, 6, 2}

round 4 : seq {1, 4, 5, 7},   result {3, 6, 2, 7}

round 5 : seq {1, 4, 5},    result {3, 6, 2, 7, 5}

round 6 : seq {1, 4},    result {3, 6, 2, 7, 5, 1}

round 7 : seq {4},    result {3, 6, 2, 7, 5, 1, 4}

 

 

 

이렇게 삭제된 현재 위치에서 K번 째 수를 찾아 가고, 그 수를 삭제하고.. 이렇게 원소가 남지 않을 때 까지 무한 반복을 하면 되는 것이다.

 

이 것을 어떻게 큐로 이용해야 할까?

 

가장 보편적인 방법은 이렇다.

K번 쨰 수가 되기 직전까지 맨 앞의 원소를 K-1 번 꺼내오고(poll) 꺼내온 원소들을 맨 뒤로 넣는다.(offer)

 

그리고 K번째로 뽑힌(poll) 원소는 출력하면 되는 것이다.

 

 

대강 이렇게 보면 된다.

 

round 1

   loop 1 : {1, 2, 3, 4, 5, 6, 7}  → {2, 3, 4, 5, 6, 7, 1} 

   loop 2 : {2, 3, 4, 5, 6, 7, 1}  → {3, 4, 5, 6, 7, 1, 2} 

   loop 3 : {3, 4, 5, 6, 7, 1, 2}  → 3 출력

 

round 2

   loop 1 : {4, 5, 6, 7, 1, 2}  → {5, 6, 7, 1, 2, 4} 

   loop 2 : {5, 6, 7, 1, 2, 4}  → {6, 7, 1, 2, 4, 5} 

   loop 3 : {6, 7, 1, 2, 4, 5}  → 6 출력

 

round 3

   loop 1 : {7, 1, 2, 4, 5}  → {1, 2, 4, 5, 7} 

   loop 2 : {1, 2, 4, 5, 7}  → {2, 4, 5, 7, 1} 

   loop 3 : {2, 4, 5, 7, 1}  → 2 출력

 

round 4

   loop 1 : {4, 5, 7, 1}  → {5, 7, 1, 4} 

   loop 2 : {5, 7, 1, 4}  → {7, 1, 4, 5} 

   loop 3 : {7, 1, 4, 5}  → 7 출력

 

round 5

   loop 1 : {1, 4, 5}  → {4, 5, 1} 

   loop 2 : {4, 5, 1}  → {5, 1, 4} 

   loop 3 : {5, 1, 4}  → 5 출력

 

round 6

   loop 1 : {1, 4}  → {4, 1} 

   loop 2 : {4, 1}  → {1, 4} 

   loop 3 : {1, 4}  → 1 출력

 

round 7

   loop 1 : {4}  → {4} 

   loop 2 : {4}  → {4} 

   loop 3 : {4}  → 4 출력

 

 

 

이렇게 가장 간단한 방법으로 알고리즘을 구성할 수 있다. 한마디로 K-1번만큼 poll과 offer을 한 뒤, K번 째 값을 poll만하고 해당 원소를 출력해주면 되는 것이다.

 

간단하게 코드로 보자면 이렇다.

 

Queue<Integer> q;	// 1~N까지 큐에 입력되어있다고 가정
int K;	// K번째 수

while(!q.isEmpty()) {

	// K-1번 앞에 있는 원소를 뒤로 보낸다.
	for(int i = 0; i < K - 1; i++) {
		int val = q.poll();
		q.offer(val);
	}

	print(q.poll());	// K번째로 나오는 원소를 삭제함과 동시에 출력한다.
}

 

 

 

 

 

 

물론 이런 방식 말고 큐 대신 리스트를 활용하여 K값을 매 번 K씩 증가시키며 해당 원소를 삭제하면서 해당 값을 출력하는 방법이 있다.

 

물론 리스트의 시작 index는 0부터 시작하고, 매 번 원소가 한 개씩 줄기 때문에 때문에 처음 시작 값 및 증가 값은 K값에 -1을 해야한다.

 

또한 중요한 점은, 참조하려는 인덱스가 입력받은 수보다 작아질 경우가 생기는데, 이럴 경우 참조 범위 밖으로 에러가 생길 수 있다. 그러니 반드시 현재 큐의 크기를 나눈 나머지 값으로 증가시켜야 한다.

 

위 예제를 그대로 예로들면 이렇다. 

 

index = 2

  → index 2 의 원소 삭제 : {1, 2, 3, 4, 5, 6, 7} 

 

index = 4 [index = (index + (K - 1)) % size     →   (2 + 2) % 6 = 4]

  → index 4 의 원소 삭제 : {1, 2, 4, 5, 6, 7}

 

index = 1  [index = (index + (K - 1)) % size     →   (4 + 2) % 5 = 1]

  → index 1 의 원소 삭제 : {1, 2, 4, 5, 7}

 

index = 3  [index = (index + (K - 1)) % size     →   (1 + 2) % 4 = 3]

  → index 3 의 원소 삭제 : {1, 4, 5, 7}

 

index = 2  [index = (index + (K - 1)) % size     →   (3 + 2) % 3 = 2]

  → index 2 의 원소 삭제 : {1, 4, 5}

 

index = 0  [index = (index + (K - 1)) % size     →   (2 + 2) % 2 = 0]

  → index 0 의 원소 삭제 : {1, 4}

 

index = 0  [index = (index + (K - 1)) % size     →   (0 + 2) % 1 = 0]

  → index 0 의 원소 삭제 : {1}

 

 

 

이런 식으로 할 수도 있다.

 

코드로 보자면 이렇다.

 

LinkedList<Integer> list;	// 1~N까지 리스트에 입력되어있다고 가정
int K;	// K번째 수

int index;	// 리스트에서 삭제할 요소를 참조할 인덱스

while(!list.isEmpty()) {

	index = (index + (K - 1)) % list.size();

	print(list.get(index));	// index위치에 있는 요소를 출력

	list.remove(index);	// index위치에 있는 요소를 삭제
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 4가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 두 가지 입력 방법을 통해 성능을 비교하려 한다.

그리고 각 입력방법에 대해 필자가 설명한 두 가지 방식의 알고리즘을 적용해보도록 하겠다. 출력 내용을 모두 StringBuilder를 사용하여 한 번에 묶은 뒤, 한 번에 출력 할 것이니 이 점 미리 알고계시길 바란다.

 

 

1 . Scanner + 알고리즘1

2 . Scanner + 알고리즘2

3. BufferedReader + 알고리즘1

4. BufferedReader + 알고리즘2

 

 

 

---

• 풀이

- 방법 1 : [Scanner + 알고리즘 1]

 

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		Queue<Integer> q = new LinkedList<>();
		
		int N = in.nextInt();
		int K = in.nextInt();
		
		
		for(int i = 1; i <= N; i++) {
			q.add(i);
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append('<');
		
		/*
		 *  마지막 부분의 출력은 > 괄호 전에 공백이 없기 때문에
		 *  일괄적으로 출력하기 위해 마지막 원소만 남겨질 때까지만
		 *  반복하고 마지막 원소는 그대로 출력한다.
		 */
		while(q.size() > 1) {
			
			for(int i = 0; i < K - 1; i++) {
				int val = q.poll();
				q.offer(val);
			}
			
			sb.append(q.poll()).append(", ");
		}

		// 마지막 원소 출력한 뒤 > 도 붙여준다.
		sb.append(q.poll()).append('>');
		System.out.println(sb);
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

중요한 점은 주석으로도 달아놓았지만, 출력 형식을 잘 보면 원소 사이사이에 쉼표(,)와 공백(" ") 이 있지만 마지막 출력 부분은 공백이 없다. 그렇기 때문에 마지막 원소 부분은 반복문으로 돌리지 말고 그 전까지만 반복문을 돌린 뒤, 마지막 원소는 따로 출력해주도록 만들었다.

 

 

---

- 방법 2 : [Scanner + 알고리즘 2]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

import java.util.Scanner;
import java.util.LinkedList;

public class Main {

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);	
		LinkedList<Integer> list = new LinkedList<Integer>();

		int N = in.nextInt();
		int K = in.nextInt();
		
		for(int i = 1; i <= N; i++) {
			list.add(i);
		}
		
		
		StringBuilder sb = new StringBuilder();
		sb.append('<');
		
		int index = 0;	// 리스트에서 삭제할 요소를 참조할 인덱스 변수
		
		while(list.size() > 1) {
			index = (index + (K - 1)) % list.size();
			
			// index위치에 있는 요소를 삭제함과 동시에 출력 
			sb.append(list.remove(index)).append(", ");
		}
		
		// 마지막으로 남은 요소 삭제함과 동시에 출력
		sb.append(list.remove()).append('>');
		System.out.println(sb);
	}
}

 

 

 

리스트 계열 중 어떤 것을 써도 무방하다. 다만 중간 삭제가 많은만큼 ArrayList보다는 약간이나마 LinkedList가 더 효율적이라 LinkedList로 했다.

 

 

 

---

- 방법 3 : [BufferedReader + 알고리즘 1]

 

 

 

방법 1에서 입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 K를 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Queue<Integer> q = new LinkedList<>();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		
		for(int i = 1; i <= N; i++) {
			q.add(i);
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append('<');
		
		/*
		 *  마지막 부분의 출력은 > 괄호 전에 공백이 없기 때문에
		 *  일괄적으로 출력하기 위해 마지막 원소만 남겨질 때까지만
		 *  반복하고 마지막 원소는 그대로 출력한다.
		 */
		while(q.size() > 1) {
			
			for(int i = 0; i < K - 1; i++) {
				q.offer(q.poll());
			}
			
			sb.append(q.poll()).append(", ");
		}

		// 마지막 원소 출력한 뒤 > 도 붙여준다.
		sb.append(q.poll()).append('>');
		System.out.println(sb);
	}

}

 

 

 

입력형식만 바꿔준 것이라 어렵진 않았을 것이다.

 

---

- 방법 4 : [BufferedReader + 알고리즘 2]

 

 

 

마찬가지로 방법 2에서 입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 

만약 매 번 리스트를 참조하여 사이즈를 알아내는 것이 조금 불편하다면 list.size 대신 변수 N을 써서 1씩 감소시켜도 된다. 

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		LinkedList<Integer> list = new LinkedList<Integer>();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		for(int i = 1; i <= N; i++) {
			list.add(i);
		}
		
		
		StringBuilder sb = new StringBuilder();
		sb.append('<');
		
		int index = 0;	// 리스트에서 삭제할 요소를 참조할 인덱스 변수
		
		while(N > 1) {
			index = (index + (K - 1)) % N;
			
			// index위치에 있는 요소를 삭제함과 동시에 출력 
			sb.append(list.remove(index)).append(", "); 
			N--;
		}
		
		// 마지막으로 남은 요소 삭제함과 동시에 출력
		sb.append(list.remove()).append('>');
		System.out.println(sb);
	}
}

 

 

 

크게 어려울 것은 없을 것이다. 코드도 그리 길지 않고, 조금만 생각해본다면 수식을 금방 완성할 수 있었을 것이다.

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 25559256  -  방법 4 : BufferedReader + 알고리즘 2

채점 번호 : 25559252  -  방법 3 : BufferedReader + 알고리즘 1

채점 번호 : 25559249  -  방법 2 : Scanner + 알고리즘 2

채점 번호 : 25559246  -  방법 1 : Scanner + 알고리즘 1

 

 

보면 큐에서 매번 원소를 빼고 넣는 것 보다 특정 인덱스를 찾아나서는 것이 훨씬 빠르다는 것을 볼 수 있다.

---

• 정리

 

이 번 문제 또한 어려운 점은 없었을 것이다. 

큐, 덱을 활용하는 문제지만 다른 방식으로도 더 효율적이게 짤 수 있다는 것을 알려주고자 다른 방법도 보여주었다.

 

대개 이러한 문제들은 조금만 노트에 정리해보다보면 공식이 어렵지 않게 나오기 때문에 일단 보이는대로 풀이를 해본 뒤 한 번 더 다른 방법은 없는지 고민해보는 것도 좋지 않을까 생각이 든다.

 

혹여 어렵거나 이해가 되지 않는 부분이 있다면 댓글 남겨주시면 최대한 빠르게 답변드리도록 하겠다.