백준 1158 - 요세푸스 문제 자바 풀이

문제 링크

문제 풀이 시간 :

문제 요약

1번부터 N번까지 사람이 원형으로 앉아 있음
순서대로 K번째 사람을 제거
모든 사람이 제거될 때까지 반복
제거되는 순서를 출력하는 문제

문제 풀이

이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.

앞에서부터 사람을 꺼내고 제거할 차례가 아니면 다시 뒤로 보내는 방식으로 생각하면 큐로 쉽게 풀 수 있다.

매번 K-1명은 뒤로 보내고 K번째 사람은 제거해서 결과에 넣으면 된다.

이 과정을 큐가 빌 때까지 반복하면 문제에서 요구하는 요세푸스 순열을 그대로 구할 수 있다.

출력 형식이 <1, 2, 3>처럼 정해져 있으므로 StringBuilder로 문자열을 만들어 한 번에 출력하면 된다.

최종 코드

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

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());

        Queue<Integer> q = new ArrayDeque<>();

        // 1번부터 n번까지 큐에 삽입
        for (int i = 1; i <= n; i++) {
            q.add(i);
        }

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

        // 큐가 빌 때까지 K번째 사람 제거
        for (int i = 0; i < n; i++) {
            // 앞에서 K-1명은 뒤로 이동
            for (int j = 0; j < k - 1; j++) {
                q.add(q.poll());
            }

            // K번째 사람 제거
            sb.append(q.poll());

            // 마지막 원소가 아니면 쉼표 추가
            if (i != n - 1) {
                sb.append(", ");
            }
        }

        sb.append(">");

        System.out.println(sb);
    }
}

1158 - 요세푸스 문제

문제 풀이 시간 :

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

5430번 - AC

1966번 - 프린터 큐

2164번 - 카드2

17070번 - 파이프 옮기기 1