CodingTEST
[백준 11866] 요세푸스 문제 (JAVA)
경걍
2023. 11. 30. 03:37
반응형
백준 11866번 문제 - 요세푸스 문제
11866번: 요세푸스 문제 0
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
www.acmicpc.net
문제 분석

- 1부터 N까지 수가 있을 때, 요새푸스 순열에 따라 제거되는 순서를 출력해라.
- 요스푸스 순열 방법
- N개의 수가 원으로 이뤄진다.
- K번째 수를 제거, K번째 수부터 다시 K번째 수를 제거 ... 모든 수가 제거될 때까지 반복
해결 키 포인트
- 시작 인덱스(index)를 K-1번째 수부터
- 모든 수가 삭제될 때까지 반복 (lists.size() > 1)
- 리스트에서 index번째 수를 출력 및 제거
- index를 index + (K-1) 를 list.size()만큼 나눈 값으로 설정
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
ArrayList<Integer> lists = new ArrayList<>();
for (int i = 1; i <= N; i++) {
lists.add(i);
}
int index = K-1;
bw.write("<");
while(lists.size() > 1) {
bw.write(lists.get((int) index)+", ");
lists.remove((int) index);
index = (index+K-1) % lists.size();
}
bw.write(lists.get(0)+">");
bw.flush();
bw.close();
}
}
반응형