[코딩 테스트/ 백준 알고리즘] 1158번 : 요세푸스 문제 (Java 풀이)

문제

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

1158번: 요세푸스 문제

---

해설

기본 테이블

 N = 7, K = 3인 케이스일 때 위와 같은 원탁이 만들어진다.

3번 삭제

1번을 기준으로 세번째 자리에 앉은 3번 사람을 삭제한다.

6번 삭제

기준을 3번의 왼쪽에 앉은 4번으로 바꿔서 세번째 자리에 앉은 6번 사람을 삭제한다.

이후 이 방식으로 테이블에 앉은 모든 사람을 삭제한다.

삭제된 사람을 순서대로 출력하면 <3, 6, 2, 7, 5, 1, 4>이 된다.

---

풀이

 이 문제는 큐를 활용하면 쉽게 해결할 수 있다.

 우선 큐에 N까지의 숫자를 차례대로 넣어준다.

 3번을 삭제하기 위해선 앞에 있는 1과 2가 나와줘야한다.

 문제에 "한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다." 라고 적혀있기 때문에 1과 2를 버려서는 안된다. 때문에 꺼낸 수를 큐의 rear에 넣어준다.

3번이 큐의 front로 왔다면, 큐에서 삭제한다. 이때는 빼낸 숫자를rear로 보내지 않아도 된다.

---

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        Queue<Integer> q = new LinkedList<>();	//큐
        for (int i = 1; i <= n; i++) {
            q.offer(i);
        }
        System.out.printf("<");	//괄호 열고
        for (int j = 0; j < n - 1; j++) {	//수가 하나 남을 때까지
            for (int i = 1; i < k; i++) {	//k-1번째 수까지 poll & offer
                int tmp = q.poll();
                q.offer(tmp);
            }
            int tmp = q.poll();
            System.out.printf("%d, ", tmp);
        }
        System.out.println(q.poll() + ">");	//마지막 수 꺼내기 & 괄호 닫기
    }
}

---

총평

 문제보다 출력 형식 맞추는 데 더 많은 고민을 했다.