[Java] Baekjoon1158: 요세푸스 문제

요세푸스 문제

2 초

256 MB

58856

28719

20405

48.052%

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

풀이

요세푸스 순열은 큐를 활용하는 대표적인 문제 중 하나입니다.

큐에 1부터 N까지 숫자들을 집어넣고 반복문을 통해 큐에 아무 원소도 없을 때까지 시행을 반복해줍니다.

 

원의 특성

원은 처음과 끝이 연결되어있습니다.

이를 큐에 원소를 집어넣고 처음 원소를 끝에 다시 집어넣는 방식으로 구현할 수 있습니다.

1 2 3 4 → 2 3 4 1  → 3 4 1 2 → 4 1 2 3 → 1 2 3 4

 

K번째마다 꺼내기

while 문과 Queue 클래스의 isEmpty() 를 조합해 큐가 텅 빌 때까지 반복문을 돌릴 수 있습니다.

while(!Q.isEmpty()) {
	Q.offer(Q.poll()); // 원소를 빼고 뒤로 넘김
}

외부에서 변수를 하나 만들고 반복문이 돌아갈 때마다 더해줍니다.

이 변수가 입력 받은 K의 배수가될 때마다 큐의 원소를 꺼내고 기록해줍니다.

 

전체 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
    Queue<Integer> Q = new LinkedList<Integer>();
    StringBuilder sb = new StringBuilder();
    Scanner sc = new Scanner(System.in);
    sb.append("<");
    
    int N = sc.nextInt();
    int K = sc.nextInt();
    
    for(int i=1; i<=N; i++) { //큐에 1부터 N까지 넣기
    	Q.offer(i);
    }
    
    int idx = 0;
    
    while(!Q.isEmpty()) {
    	idx ++; // idx로 실시간 순번을 기록
    	
    	if(idx%K==0) { // idx가 K의 배수가 될 때 해당 원소를 꺼내고 기록
    		sb.append(Q.poll()+", ");
    	}else {
    		Q.offer(Q.poll()); // 그 외에는 빼고 뒤로 넘김
    	}
    }
    sb.setLength(sb.length()-2); // 마지막에 더했던 ', ' 를 삭제
    sb.append(">");
    System.out.println(sb.toString());
}
}