문제
1번부터 N번까지 N명이 원형으로 앉아있다. K번째 사람을 반복적으로 제거하여 모두 제거될 때까지의 순서(요세푸스 순열)를 구하라.
입력
첫째 줄에 N과 K가 주어진다 (1 이상 K 이상 N 이상 5,000 이하).
출력
요세푸스 순열을 <n1, n2, ..., nN> 형태로 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 3 | <3, 6, 2, 7, 5, 1, 4> |
풀이
큐를 사용하여 원형 순회를 시뮬레이션한다. K-1번은 큐의 앞에서 빼서 뒤로 넣고, K번째는 제거하여 결과에 추가한다.
- 1부터 N까지의 수를 큐에 넣는다
- K 카운트를 감소시키며 0이 아닌 동안 앞의 원소를 뒤로 보낸다 (왼쪽 회전)
- 카운트가 0이 되면 해당 원소를 제거하고 결과 문자열에 추가한다
- 마지막 한 명은 별도로 처리하여 쉼표 없이 추가한다
핵심 아이디어: 큐의 앞에서 빼서 뒤로 넣는 연산으로 원형 배열의 순회를 자연스럽게 구현할 수 있다.
코드
package com.ssafy.an.day049;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Day16BOJ1158요세푸스문제 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
Queue<Integer> q = new LinkedList<>();
int N = sc.nextInt();
int K = sc.nextInt();
sb.append("<");
for (int i = 1; i <= N; i++) {
q.add(i);
}
int k = K;
while (!q.isEmpty()) {
k--;
if (k != 0) {
q.add(q.poll());
} else if (q.size() != 1) {
sb.append(q.poll()).append(", ");
k = K;
} else // 마지막에는 ','를 붙히면 안되서, 1되면 탈출
break;
}
sb.append(q.poll()).append(">");
System.out.println(sb);
sc.close();
}
}복잡도
- 시간: O(N * K) — N명을 제거하며 각각 최대 K번 회전
- 공간: O(N) — 큐