Today Sulim Learned
silver 5. 요세푸스 문제 (1158)
02 Mar 2022 | 알고리즘 프로그래밍 자바문제
N명의 사람이 원을 이루며 앉아있고, 양의 정수 K가 주어질 때, 순서대로 K 번째 사람을 제거. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나가고, N명의 사람이 모두 제거될 때까지 반복. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 함
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성
입력: 첫 줄에는 N과 K가 빈 칸을 사이에 두고 순서대로 주어짐 ($1 <= K <= N <= 5,000$)
출력: 요세푸스 순열 출력
풀이
-
아이디어: 연결 리스트(Linked List) 활용. K번째인지 확인해주는 변수를 만들어
- K번째일 경우, 연결 리스트의 첫 번째 값을 꺼내옴
- K번째가 아닐 경우, 연결 리스트의 첫 번째 값을 꺼내와 마지막 원소로 다시 넣어줌
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); // 요세푸스 순열을 저장할 변수 StringTokenizer st = new StringTokenizer(br.readLine()); Integer N = Integer.parseInt(st.nextToken()); Integer K = Integer.parseInt(st.nextToken()); Integer count = 1; // K번째인지 확인해줄 변수 // 1 ~ N을 가지는 리스트 생성 ArrayList<Integer> nums = new ArrayList<Integer>(); for (Integer i = 0; i < N; i++){ nums.add(i+1); } LinkedList<Integer> link = new LinkedList<Integer>(nums); // 1~N의 값을 가지는 연결 리스트 생성 while(link.size() > 1) { // 연결 리스트의 길이가 1보다 클 때 if(count % K == 0) { // K번째 수인 경우 sb.append(link.poll() + ", "); // 첫 번째 원소의 값을 빼와 요세푸스 순열에 넣어줌 } else { // K번째 수가 아닌 경우 link.add(link.poll()); // 첫 번째 원소의 값을 빼와 연결 리스트의 마지막 원소로 넣어줌 } count += 1; // count 값 1 증가 } sb.append(link.poll()); // 마지막 남은 값을 요세푸스 순열에 넣어줌 System.out.println("<" + sb + ">"); // 결과 출력 } }- 마지막 남은 값을 따로 넣어주는 이유는 마지막 값을 넣을 때 ‘, ‘를 요세푸스 순열에 포함시키지 않기 위함
