/<BOJ 백준 1158번> 요세푸스 문제 - Java

문제 1158번 : 요세푸스 문제

문제 해설

N명의 사람이 모두 제거될 때 까지, 순서대로 K번째 사람을 제거하는 과정을 계속 진행하는 요세푸스 문제는 K-1번째 사람을 남겨두고 K번째 사람을 제거하면 된다. 이 아이디어는 자료 구조 "큐(Queue)"를 이용하여 해결할 수 있다. 큐는 먼저 들어온 데이터가 먼저 나가는 형식 First-In-First-Out 자료구조이다. 문제 제시된 바와 같이 순서대로 K번째 사람을 제거하는 것이므로 K-1번째 사람은 큐에서 제거한 후, 맨 뒤로 다시 추가하면 된다. 이 과정을 큐가 비어있을 때 까지 반복하면 된다.

 

자바에서 Queue 인터페이스는 LinkedList 클래스에서 구현되어 있다. 

 

이를 코드로 구현하면 다음과 같다.

 

while (!queue.isEmpty()) {
    for (int i = 0; i < K - 1; i++) {
        queue.offer(queue.poll()); // K-1번째까지의 수를 큐 뒤로 이동
    }
    sb.append(queue.poll());
}

 

while 반복문에서 queue는 LinkedList의 객체이고 LinkedList는 List 인터페이스를 구현하였다. List에서 isEmpty()의 시간복잡도는 일반적으로 O(1)이다. 또한 queue의 데이터를 추가하는 offer() 메소드와 삭제하는 poll() 메소드 역시 시간복잡도 O(1)을 갖는다. 이 연산들을 K - 1회 반복한다. 따라서 위 로직의 시간복잡도는 O(K - 1)이다.

 

여기서 sb는 StringBuilder의 객체로 정답을 하나로 묶어주기 위해 사용하였다. 전체 코드는 글의 마지막 부분에 올려두었다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public void solution() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        Queue<Integer> queue = new LinkedList<>();
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        for(int i = 1; i <= N; i++) {
        	queue.offer(i);
        }

        sb.append("<");
        while (!queue.isEmpty()) {
            for (int i = 0; i < K - 1; i++) {
                queue.offer(queue.poll()); // K-1번째까지의 수를 큐 뒤로 이동
            }
            sb.append(queue.poll());
            if (!queue.isEmpty()) {
            	sb.append(", ");
            }
        }
        sb.append(">");

        System.out.println(sb);	
    }

    public static void main(String[] args) throws Exception{
    	new Main().solution(); 
    }

}