Baekjoon 문제 풀기 (11866번 : 요세푸스 문제 0) Java

11866번 : 요세푸스 문제 0

1. 문제읽기

---

처음에 문제를 잘못이해하고 제거된 자리는 그대로 남고 순서를 계속 세는 줄 알았다.
다시 보니 제거 된 사람의 자리는 없어지고 순서를 세어야 한다.

2. 제출 코드

---

테케도 통과를 못해서 제출도 못했다.
저번에 원형 큐를 공부해서 원형 큐를 구현해서 문제를 풀려고 했는데 실패했따.
맞는 순서가 되면 배열의 값을 0으로 초기화 하고 넘어가려고 했는데, 0일 때 continue를 사용하려는 접근까지는 좋았지만 그 뒤에 index값을 또 +1을 시켜버려서 정답과는 멀어지게 되었다..
점점 조건이 늘어나서 코드가 지저분해지는 것을 보고 음.. 아니겠군 하고 정답을 보았다.

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

public class BOJ11866 {
    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());
        br.close();
        int[] arr = new int[n+1];
        // 1부터 n까지 배열 채우기
        for(int i = 1; i <= n; i++) {
            arr[i] = i;
        }
        List<Integer> ans = new ArrayList<>();
        int cnt = 1;  // 순서
        int index = 1;  // 인덱스
        while(ans.size()!=n) {
            if(arr[index]==0) {
                if(index > arr.length-1) {
                    index = 1;
                } else {
                    index++;
                }
                continue;
            }
            cnt++;
            if(index > arr.length-1) {
                index = 1;
            } else {
                index++;
            }
            if(cnt%k==0) {  // 순서가 맞으면 제거
                ans.add(arr[index]);
                arr[index] = 0;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i : ans) {
            sb.append(i+ " ");
        }
        System.out.println(sb);
    }
}

3. 공부할 것

---

k-1번만큼 반복을 시켜 앞의 값을 뒤로 보낸다.
그러면 맨 앞에는 제거해야 할 순서의 값이 존재하게 된다.
이 것을 queue의 값이 1개가 남을 때 까지 반복한다. (출력값의 마지막이 공백이 없기 때문에)
원리를 알고 나니 쉬웠다.

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

public class BOJ11866 {
    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());
        br.close();
        Queue<Integer> queue = new LinkedList<>();
        // 큐에 값 추가하기
        for(int i = 1; i <= n; i++) {
            queue.add(i);
        }

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

        while(queue.size() > 1) {
            for(int i = 0; i < k-1; i++) {
                queue.offer(queue.poll());
            }
            sb.append(queue.poll()).append(", ");
        }

        // 마지막 원소 출력 뒤 >를 붙여준다.
        sb.append(queue.poll()).append(">");
        System.out.println(sb);
    }
}