[백준] 요세푸스 문제 0 (JAVA)

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

 

 

요세푸스 순열을 이용한 문제다.

총 인원과 양의 정수 순번이 주어진다.

순번마다 모든 인원을 순환하며 인원을 제거한다. 제거된 사람들의 순서를 반환한다.

 

테스트케이스 1) (7명의 인원과 3의 순번마다 제거)

1. 3번째 사람인 3번 제거
2. 6번 제거
3. 7번을 초과하면 1로 가서 2 제거
4. 3, 6번은 제거되었으므로 7 제거
5. 1로 가서 2, 3은 제거되었으므로 5 제거
6. 1 제거
7. 4 제거

출처 : https://velog.io/@gayeong39/%EB%B0%B1%EC%A4%80-11866-%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4-%EB%AC%B8%EC%A0%9C-0-JAVA

최종적으로 <3, 6, 2, 7, 5, 1, 4> 반환

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

// 백준 요세푸스 문제 0
// n k 를 입력받음
// n -> 총 인원
// k -> k만큼 돌아가면서 죽여버림
// n명의 사람들이 빙글 둘러서 앉아있다. 매 턴 k번째 사람을 죽인다.
// 한바퀴를 돌았다면 다시 1번 사람부터 죽인다. 모두 죽을 때까지 반복
// ex) 7 3 -> <3 6 2 7 5 1 4>
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 people = Integer.parseInt(st.nextToken());
        int turn = Integer.parseInt(st.nextToken());

        // 사람 생존 여부 배열(살아있다면 0, 죽으면 1), 제거된 인원의 수, 턴, 죽이는 순서(턴 증가에 따라 1씩 까임)
        int[] arr = new int[people];
        int kill = 0;
        int i = 0;
        int tmp = turn;

        // 첫번째 꺽쇠
        System.out.print("<");
        while (kill < people) {
            // i가 마지막 순서까지 갔다면 처음 인원의 순번으로 돌아감, 아니라면 다음 순번
            if (arr[i] == 1) {
                if (i == people - 1) {
                    i = 0;
                } else {
                    i++;
                }
                continue;
            } else if (tmp == 0 && arr[i] == 0) {
                kill++;
                // 7번째가 0으로 들어감
                int p = i == 0 ? people : i;
                // 꺽쇠 컨트롤
                if (kill == people)
                    System.out.print(p + ">");
                else
                    System.out.print(p + ", ");
                // 제거된 인원은 1로 변경
                arr[i] = 1;
                tmp = turn;
            }
            // i가 배열의 끝까지 가면 돌아옴
            i = (i + 1) % people;
            tmp--;
        }
    }
}

 

BufferedReader와 StringTokenizer를 이용해 입력 속도를 향상시켰다.

초기 배열의 크기는 참가 인원의 수대로 했고 생존했다면 0, 제거됐다면 1로 표시

 

while문을 이용해 제거된 사람들이 참여 인원수와 같아질때까지 반복했다.

마지막 순번의 인원을 거친다면 처음 순번의 인원으로 돌아감.

 

순번 turn마다 인원이 제거되어 그 순번을 출력하게 하고

마지막으로 제거된 인원이 아니라면 추가로 ,도 함께 출력한다.

 

제거된 인원은 1로 변경되어 건너뛰게 했다.

 

마지막으로 제거된 인원은 >를 함께 출력한다.

 

사실 이 문제는 큐를 이용해서 해결하라고 백준에 추천돼있지만 사용하지 않고 풀어보았다.

큐를 이용하면 좀 더 간단하게 풀 수 있을 것.

새해 복 많이 받으세요