백준 1158 - 요세푸스 문제

깃허브:

https://github.com/MSIQOC/BOJ/blob/master/b1158_%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4%EB%AC%B8%EC%A0%9C.java

 

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

문제만 보고는 처음에 요구하는 것이 무엇인지 잡아내기가 힘들었던 것 같다.

문제에 있는 예제 입력 1을 보고 문제가 요구하는 것을 그림으로 나타내보았다. n은 7, k는 3이기 때문에 말그대로 7명의 사람들이 테이블을 둘러싸서 앉아있고 1부터 시작해서 세번째 턴이 될 때마다 한명씩 제거해주는 형태를 가지고있다.

한쪽으로 들어가고 다른 한쪽으로 빠지는 구조를 가지고 있는 큐를 이용하면 간단하게 구현이 가능하다. 위 그림을 예로 들면 극초반에 첫번째 턴과 두번째 턴은 1과 2이기 때문에 큐에서 빼서 다시 뒤로 넣어주고, 세번째 턴인 3은 그대로 큐에서 빼내서 값을 출력해주면 된다. 이렇게 큐가 다 빌 때까지 이 과정을 반복해주면 된다.

 

 

import java.io.*;
import java.util.*;
public class b1158_요세푸스문제 {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);
        Queue<Integer> q = new LinkedList<Integer>();
        int n = sc.nextInt();
        int k = sc.nextInt();
        for(int i=1; i<=n; ++i)
            q.offer(i);
        int num=1;
        System.out.print("<");
        while(!q.isEmpty()) {
            if(q.size() == 1) {
                int p = q.poll();
                System.out.print(p+">");
            }
            else if(num==k) {    
                int p = q.poll();
                System.out.print(p+", ");
                num = 1;
            }
            else {
                int p = q.poll();
                q.offer(p);
                ++num;
            }
        }
    }
}