[Java] BOJ 11866 요세푸스 문제 0

문제 

문제 링크 https://www.acmicpc.net/problem/11866

• 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다.
• 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
• 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
• 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

아이디어

• while문을 돌리면서 시작점의 위치에서 K번째 뒤가 현재 인원의 최댓값보다 클 경우에는 처음으로 돌아가서 다시 세기 위해 ((시작점 + K - 1) % 남은 사람 수)를 하고 아닐 경우에는 시작점에서 K - 1을 더한 값을 다시 시작점으로 잡는다. 
• 그리고 그렇게 사람을 한명씩 뺄때마다 ArrayList에서도 해당 위치의 값을 remove해준다.
• 그렇게 사람들의 번호가 들어있는 ArrayList가 빈 값이 되면 While문을 종료한다. 

겪은 시행착오

• While문 안에 있는 if문식이 생각처럼 돌아가지 않아서 여러번 시행착오를 겪은 끝에 해결할 수 있었다..ㅜㅜ

오늘도 열심히 했다..!

코드

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

public class BOJ11866 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 숫자를 저장할 arrayList
        List<Integer> round = new ArrayList<Integer>();
        List<Integer> result = new ArrayList<Integer>();

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

        // 순서대로 숫자를 집어넣음
        for(int i = 1; i <= N; i++){
            round.add(i);
        }

        // 시작위치
        int start = 0;

        while(true){
            // 만약 시작위치에서 K번째 뒤가 최대 사람수를 넘겼다면
            if(start + (K - 1) > (round.size() - 1)){
                // 다시 앞으로 가서 빼고 남은 수 만큼 카운트
                start = (start + (K - 1)) % round.size();
            }
            else{
                // 최댓값을 넘어가지 않는다면 K번째 뒤를 시작점으로 옮김
                start = start + (K - 1);
            }

            // 결과를 저장할 arrayList에 바뀐 시작점에 있는 사람을 저장
            result.add(round.get(start));
            // 결과 값에 저장됐으면 원래 arrayList에서도 제거해줌
            round.remove(start);

            // 사람들 저장해놓은 arrayList가 비었다면 종료
            if(round.isEmpty()){
                break;
            }
        }

        sb.append("<");

        for(int i = 0; i < N; i++){
            if(i == N - 1){
                sb.append(result.get(i) + ">");
            }
            else{
                sb.append(result.get(i) + ", ");
            }
        }

        System.out.println(sb);
    }
}