[JAVA] 백준 1158번 【요세푸스 문제】

---

처음에 문제를 잘 이해못했었던 문제다.

 

N 명의 사람들을 K 번째 사람을 계속해서 제외한다고 하는데,

 

예제 처럼, 7명의 사람을 3번째 사람을 계속해서 제외한다는 의미는

 

1 2 3 4 5 6 7

 

이렇게 사람이 있다고 할 때,

 

 

 

1 2 3 4 5 6 7

 

1 → 2→ 3 이므로

3번째 사람을 제외한다.

 

---

 

1 2 3 4 5 6 7

 

 

4 → 5 → 6 이므로

그다음 3번째인 6번째 사람을 제외하고

 

---

 

1 2 3 4 5 6 7

 

 

7 → 1 → 2 이므로

그다음 3번째인 2번째 사람을 제외하고

 

---

 

1 2 3 4 5 6 7

 

이미 제외된 사람은 순서에서 빼야하므로

 

4 → 5 → 7 이 되어

그다음 3번째인 7번째 사람이 제외되야 한다.

 

---

 

1 2 3 4 5 6 7

 

그 다음은 마찬가지로, 1 → 4 → 5 가 되어

 

5번째 사람이 제외되야 하고

 

---

 

1 2 3 4 5 6 7

 

1 → 4 → 1 

 

1번째 사람이 제외되고

 

---

1 2 3 4 5 6 7

 

마지막은 4번째 사람이 제외되는 것이다.

 

 

 

큐의 성질을 이용해서, 큐는 제일 앞에 있는 원소를 poll로 빼낼 수 있으므로

 

K번째에 속하지 않는 경우 poll을 해줌과 동시에 add를 해주어 큐의 뒤쪽에 배치시키고

 

K번째에 속하는 경우 poll을 해주어 제거하고 add는 따로 해주지 않는 방법으로 구현하였다.

 

그리고 출력할때 <  > 괄호 안에 넣어서 출력해야하는데, 이 부분 구현하는게 은근 까다로웠다..

 

StringBuilder 를 만들고 append 해준 뒤, 삭제하는 방식으로 구현하였다.

 

package October.Lecture.Date221014.insertion;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class No_1158 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        StringBuilder result = new StringBuilder();
        Queue<Integer> queue = new LinkedList<>();
        
        for (int i = 1; i <= N; i++) {
            queue.add(i);
        }

        int count = 1;
        result.append("<");
        while (queue.size() != 0) {

            if (count == K) {
                result.append(queue.poll() + ", ");
                count = 1;
                continue;
            }
            ++count;
            queue.add(queue.poll());
        }
        result.append(">");
        result.deleteCharAt(result.length() - 3);
        result.deleteCharAt(result.length() - 2);
        System.out.println(result);

    }
}