[백준] 단계별로 풀어보기(단계:19,큐/덱,JAVA)11866번, 요세푸스 문제 0

문제 링크

11866번: 요세푸스 문제 0

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

기본적으로 큐는 FIFO(선입선출)의 자료구조를 가지고 있습니다.

FIFO는 먼저 들어간 데이터들이 출력할 때 먼저 나온다는 이야기입니다.

예를 들어 3, 2, 1을 순서대로 큐에 저장한 뒤 하나씩 꺼내보겠습니다.

1. 3을 큐에 넣었을 때

3

2. 2을 큐에 넣었을 때

3

2

3. 1을 큐에 넣었을 때

3

2

1

4. 큐에 하나의 자료를 출력하라는 명령이 떨어졌을 때

3

2

1

5. 다시 자료를 출력하라는 명령이 떨어졌을 때

2

1

위에 표를 보면 가장 먼저 저장된 데이터가 먼저 출력되는 것을 볼 수 있듯이 큐는 FIFO형태의 자료구조입니다.

Java에서 큐를 표현하려면 LinkList<>()로 선언해주어야 하므로 큐를 선언해주었습니다.

문제에 내용을 살펴보면 간단한 알고리즘이 발견됩니다.

1. K-1번째까지 큐에서 데이터를 꺼내서 큐에 다시 저장합니다.

2. K번째를 꺼내서 결과에 저장합니다.

3. 큐에 데이터가 없을 때까지 반복합니다.

예제 입력1로 살펴보자면

N=7, K=3

1234567 -> 456712

456712 -> 71245

71245 -> 4571

4571 -> 145

145 -> 14

14 -> 4 

4  -> empty -> 반복 종료

결과 = 3 6 2 7 5 1 4

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 반복문을 통해서 큐에 번호를 초기화하였습니다.
• 반복문을 통해 큐에 내용을 K-1번  poll하고 offer를 합니다.
• K번째 데이터를 poll하여 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과를 출력하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static Queue<Integer> queue = new LinkedList<>();	//인원 순서 저장 큐
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//입력 값을 받는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		//결과 값을 출력하는 BufferedWriter
       		//-------입력값 저장, 큐 초기화-----------
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		bw.write("<");
		for(int i=1;i<=N;i++)
			queue.offer(i);
        	// K번째 인원 구하는 연산
		for(int i=1;i<N;i++) {
			for(int j=1;j<K;j++) {
				int temp = queue.poll();
				queue.offer(temp);
			}
			bw.write(queue.poll() + ", ");	//결과 BufferedWriter에 저장
		}
		bw.write(queue.poll() + ">\n");
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
}