백준_1158 요세푸스 문제(자바) / 자료구조

시간 & 메모리 제한

문제

입력 & 출력

큐(Queue)를 이용한 문제풀이

package com.Back;

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

/* 1. 1 ~ N -> Q
 * 2. K-1번째 사람들 -> Q의 맨뒤로 보내기
 * 3. K번째 POLL -> 출력
 * 4. Q 안의 사람들이 1명 남을때 까지 반복
 * */
public class Back_1158 {

	public static void main(String[] args) throws Exception {
		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()); // 삭제될 순서
		
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		
		Queue<Integer> q = new LinkedList<Integer>();
		
		// 1~N개 OFFER
		for (int i = 1; i <= N; i++) {
			q.offer(i);
		}
		
		//N-1 명의 사람들에 대해 작업
		while(q.size() !=1) {
			for(int i = 0 ; i < K-1;i++) {
				q.offer(q.poll());
			}
			
			//K번쨰 사람은 삭제
			sb.append(q.poll()+", ");
		}
		
		//Q 안에 남은 사람 1명
		sb.append(q.poll()+">");
		
		System.out.println(sb);
	}

}

- 이 문제는 자료구조의 큐를 이용하면 풀 수 있는 문제이다.