[백준] 11866번 : 요세푸스 문제0 자바(JAVA) 풀이

문제

---

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

 

---

문제 탐색하기

• 요세푸스 : 1부터 시작하여 K-1개의 수를 건너뛰고 그 다음 K번째 수를 제거, 이 과정이 N명의 사람이 모두 제거될 때까지 반복
• 순서대로 삽입/삭제가 일어나므로 Queue를 활용하여 구현
• K-1 만큼 건너뛰고 K번째 사람을 삭제하기 위해서 큐에 있는 데이터를 K-1만큼 꺼내서 뒤로 보내고 K번째 사람을 제거

---

코드 설계하기

1. 사람의 수 N과 매번 제거될 사람의 위치 K를 입력받는다
2. 큐를 이용해서 사람들을 순서대로 입력
3. K-1만큼 건너뛰고 K번째 사람을 제거
   • 맨 앞에 있는 사람을 제거하고 다시 큐의 맨 뒤에 추가
   • 이 과정으로 K-1번째까지의 사람을 뒤로 보내고 K번째 사람 제거
4. K번째 사람 제거 될 때 StringBuilder 객체에 추가
5. 모든 사람이 제거(큐가 공백일 때) 될 떄까지 3,4 과정 반복
6. 출력 형태에 맞춰서 결과 출력

가능한 시간복잡도

입력 범위 ( 1 ≤ K, N ≤ 1000)

1. 큐에 사람 추가하기(초기화)
   • N명의 사람을 큐에 추가하는데 걸리는 시간 복잡도 O(N)
2. 사람을 뒤로 보내는 작업
   • 큐의 첫번째 요소를 뒤로 보내는 작업은 한 번에 O(1) 시간 복잡도를 가짐
   • 각 사람이 제거될 때마다 K-1번 반복되므로 시간 복잡도 O(K)
3. 사람 제거
   • poll()로 큐에서 제거하는데 걸리는 시간 복잡도 O(N)
4. 전체 시간 복잡도 시간 복잡도 O(N*K)

---

풀이 코드

※ 큐에 값을 추가하는 경우에 add와 offer이 있는데, 값 추가에 실패했을 경우 add 는 IllegalStateException, offer 는 false를 리턴하므로 offer 사용함.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder("<");
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		Queue<Integer> queue = new LinkedList<Integer>(); // queue 변수 생성
		for(int i=1;i<=N;i++) {
			queue.offer(i); // 큐에 값 입력
		}
		
		while(!queue.isEmpty()) {
			// K-1 만큼 뛰고
			for(int i=0;i<K-1;i++){
            	// 첫번째 값을 출력하면서 삭제함과 동시에 값 추가 -> 첫번째 값을 맨 뒤로 보냄
				queue.offer(queue.poll()); 			
			}
			// 해당 데이터 삭제하면서 출력할 문자열에 저장
			sb.append(queue.poll()+", ");
			
			// 마지막인 경우 쉼표 제거
			if(queue.size() == 0) {
				sb.delete(sb.length()-2, sb.length());
			}
		}
		sb.append(">");
		
		System.out.println(sb);
		
	}
}