[자바] 백준 1158번 요세푸스 문제

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

 

[문제 이해]

원을 이루어서 사람들이 서있으면 한 명씩 제거해가는 문제였는데 여기서 제일 큰 문제는 "deque에서 어떻게 순회하도록 만드는가" 였다.

N과 K가 주어졌을 때, N명의 사람 중 K번째 사람이 계속 제거되는 문제라 문제 자체를 이해하는데에 있어서는 큰 어려움은 없었던 것 같다.

 

[문제 풀이]

생각한 방법은 1부터 N까지 모두 덱에 저장하고 N에서 K번째 수를 계속 빼는 방식이었는데 "순회"를 계속 생각하다보니까 다른 방법이 생각났다 !!! 일단 deque는 K부터 저장하도록 해서 N까지 저장하고 앞 쪽에 남은 수는 (ex. K = 3이면 1, 2) N 뒤에 저장하도록 수정하였다. 가장 앞의 원소부터 제거하면서 K-1개 만큼만 poll을 통해 앞의 원소를 제거했다가 다시 뒤쪽에 삽입하는 방식으로 코드를 구현해보았다.

출력할 때도 가장 마지막이라면 ", " 없이 그냥 출력해야했기에 크기를 확인하는 코드를 추가하여 처리해주었다. deque의 poll(), add()에 대해서 제대로 이해할 수 있었던 문제였다.

 

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

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());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        Deque<Integer> deque = new LinkedList<>();
        int[] arr = new int[N];

        for(int i = K; i <= N; i++){
            deque.add(i);
        }

        for(int i = 1; i < K; i++){
            deque.add(i);
        }

        for(int i = 0; i < N; i++){
            arr[i] = deque.remove();
            for(int j = 0; j < K-1; j++){
                deque.add(deque.poll());
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write("<");
        for(int i = 0; i < arr.length; i++){
            bw.write(String.valueOf(arr[i]));
            if(!(arr.length - 1 == i))
                bw.write(", ");
        }
        bw.write(">");
        bw.flush();
        bw.close();
    }
}