문제 출처

단계별로 풀어보기 > 스택 큐 덱 > 요세푸스 문제 0
https://www.acmicpc.net/problem/11866

문제 설명

1~N번까지의 사람이 원을 이루고, 양의 정수 K가 주어질 때,
순서대로 K번째 사람들을 제거한다.
해당 과정을 계속 반복하여 모든 사람이 제거 될 때까지 반복한다.
진행한 과정을 출력하라

접근 방법

count를 1로 설정하고, count가 K가 될 때마다 1로 초기화 한다. 해당 과정에서 count가 k가 되었을 때는 처음 순서가 저장된 큐에서 아예 제거하여 결과 큐에 삽입한다.
count가 k가 아닌 경우에는 처음 순서 저장 큐에서 poll 하여 다시 offer해준다.

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

public class 요세푸스_문제_0 {
    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());
        StringBuilder sb = new StringBuilder();

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Deque<Integer> dq = new ArrayDeque<>();

        for(int i = 0; i<N; i++){
            dq.addLast(i+1);
        }

        sb.append("<");

        int count = 1;
        while(!dq.isEmpty()){
            if(count == K){
                count = 1;
                int j = dq.pollFirst();
                q.offer(j);
                continue;
            }
            else{
                int j = dq.pollFirst();
                dq.offerLast(j);
            }
            count++;
        }

        while(q.size() != 1){
            sb.append(q.poll()).append(", ");
        }

        sb.append(q.poll());

        sb.append(">");

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

Review

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 요세푸스_문제_0_review {
    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 T = Integer.parseInt(st.nextToken());

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

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

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

        int count = 1;

        while(q.size() != 1){
            if(count == T ) {
                sb.append(q.poll()).append(", ");
                count = 1;
            } else {
                int k = q.poll();
                q.offer(k);
                count++;
            }
        }

        sb.append(q.poll()).append(">");

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();


    }
}

알게된 점

처음에는 앞과 뒤 연산 모두 필요한 줄 알고, 큐 하나를 Deque로 만들어서 풀려했으나, 일반 큐 삽입 삭제 과정으로 충분해서 그냥 두고 사용했다.
Queue를 한개만 사용하고도 풀 수 있다는 것을 알았다.
Review 때 풀어봐야겠다.

Review
어렵지 않게 풀었는데 count == T 조건을 실수로 count == 3으로 적었었다.

문제푼 흔적

Review