[Java] 백준(실버-4) 11866번 - 요세푸스 문제 0

문제 풀이

---

1부터 N까지 나열된 수에서 K번째 수마다 차례대로 뽑아낸 수열을 출력하면 되는데, 큐를 이용하면 쉽게 풀 수 있다.
예제를 살펴보면 다음과 같다.

N=7, K=3
[1,2,[3],4,5,6,7] -> [3]
[1,2,4,5,[6],7] -> [3,6]
[1,[2],4,5,7] -> [3,6,2]
[1,4,5,[7]] -> [3,6,2,7]
[1,4,[5]] -> [3,6,2,7,5]
[[1],4] -> [3,6,2,7,5,1]
[[4]] -> [3,6,2,7,5,1,4]

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

아이디어 도출

• 1부터 N까지의 수가 저장된 큐를 순회하며 K번째 수가 되기 전(K-1번 만큼)까지 큐에서 꺼내서(poll) 맨 뒤로 넣는다.(offer)
• K번째 수를 꺼내서 출력한다.

간단하게 정리하면 K-1번 만큼 큐에서 꺼내고 넣다가, K번째에는 꺼내서 출력만 하면 된다.
바로 코드를 작성해보자.

StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());

Queue<Integer> numbers = new LinkedList<>();
for(int i=1; i<=N; i++) {
    numbers.offer(i);
}

N과 K를 입력받고 하나의 큐를 선언하고 1부터 N까지의 수를 저장한다.

StringBuilder sb = new StringBuilder();
sb.append("<");

while(numbers.size() > 1) {
    for(int i=0; i<K-1; i++) {
        numbers.offer(numbers.poll());
    }
    sb.append(numbers.poll()).append(", ");
}

sb.append(numbers.poll()).append(">");
bw.write(sb.toString()+"\n");

문제 출력 요구사항을 보면 수열 혈태인 <1,2,3> 형태로 출력해야 하기에 StringBuilder를 이용한다.
큐의 원소가 1개 남을 때까지 K-1번 만큼 큐에서 추출하고(poll) 맨 뒤에 삽입(offer)하다가 K번째 수가 되면 추출(poll)하여 StringBuilder에 넣는다.
그렇게 while문 종료후 마지막 남은 1개의 원소를 추출(poll)하고 >를 넣어 요구 출력사항을 만족시키면 된다.

작성코드

---

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Queue<Integer> numbers = new LinkedList<>();

        for(int i=1; i<=N; i++) {
            numbers.offer(i);
        }

        StringBuilder sb = new StringBuilder();
        sb.append("<");

        while(numbers.size() > 1) {
            for(int i=0; i<K-1; i++) {
                numbers.offer(numbers.poll());
            }
            sb.append(numbers.poll()).append(", ");
        }
        
        sb.append(numbers.poll()).append(">");
        bw.write(sb.toString()+"\n");

        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• 단순히 큐의 선입선출(FIFO) 성질을 이용만 하는 것이 아니라 추출하고 삽입하는 과정에서 문제의 요구사항을 어떻게 충족시킬 수 있을지 고민하여 알고리즘 아이디어를 도출할 수 있었다.

출처

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.