[백준] 1158: 요세푸스 문제

이제부터 c++이 아닌 java로 문제를 푸려고한다.

자료구조를 익혀야하므로, 기존 골드 문제들을 푸는 것보다는 실버부터 차근차근 푸는 것이 좋을 것 같다.

 

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

1158번: 요세푸스 문제

 

요세푸스 문제는 특정한 순서대로 사람을 제거시켜 나가는 문제이다.

큐를 이용해서 풀면 쉽게 풀 수 있다.

 

Scanner 대신 BufferedReader

Scanner와 BufferedReader 모두 문자열을 읽는데 사용하지만, BufferedReader가 Scanner보다 훨씬 빠른 속도를 제공한다.

대신 BufferedReader의 경우 예외 처리를 해주어야하는데, try-catch로 잡는 것보다는 throws를 이용해 IOException을 던져주자.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        //1. 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        
        //2. 요세푸스 문제 로직 수행
        Queue queue = new LinkedList<Integer>();
        IntStream.range(1, N + 1).forEach(queue::add);

        ArrayList result = new ArrayList();
        int cnt = 0;
        while (!queue.isEmpty()) {
            int data = (int) queue.remove();
            cnt++;

            if (cnt % K == 0) {
                result.add(data);
            } else queue.add(data);
        }
        // 3. 정답 출력
        System.out.print("<");
        for (int i = 0; i < result.size() - 1; i++) {
            System.out.print(result.get(i) + ", ");
        }
        System.out.print(result.get(result.size() - 1));
        System.out.print(">");
    }
}