[백준] JAVA 자바 : 요세푸스 문제 (1158번)

---

요세푸스 문제를 푸는 알고리즘을 만드는 문제이다.

처음에는 문제를 이해하는 게 되게 어려웠다. 아니 T가 3이면 계속 3번째 사람만 출력되는 거 아닌가??
그런데 그런 게 아니라… 시작하는 사람은 제거되는 사람의 인덱스에서 시작하는 거였다.
그러니까 처음에는 3번째 사람이 빠지면, 그 다음 사람은 3+3인 6번째 사람이 빠지는 구조!

이 문제를 코딩하는 데에도 상당히 고민을 많이 했다.
큐를 2개를 써야 하나…? 그런데 큐를 2개를 쓰면 양쪽 큐에 요소가 T-1개 남은 시점부터는 원하는 방향으로 요소를 꺼낼 수가 없게 돼서…

그런데 굳이 큐를 2개를 사용하지 않고, 큐를 하나만 사용해도 쉽게 해결할 수 있었다…
큐의 앞 요소를 빼서 다른 큐에 넣는 게 아니라 큐 자기 자신의 맨 뒤에 갖다 넣으면 되는 거였음!

즉 T-1번까지의 요소는 전부 빼서 맨 뒤로 옮기면, 이제 그 상태에서 poll()을 하면 T번째 요소를 뺄 수 있게 된다.
이걸 큐가 빌 때까지 반복하면 되는 것!

import java.util.Queue;
import java.util.LinkedList;
import java.io.*;

public class Josephus_1158 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Queue<Integer> queue = new LinkedList<>(); // 자바에서 기본 제공되는 큐를 사용하려면 이렇게 해야 한다.
        
        String str = br.readLine();
        int N = Integer.parseInt(str.split(" ")[0]);
        int T = Integer.parseInt(str.split(" ")[1]);
        
        for (int i=1; i<=N; i++) {
            queue.offer(i); // 1부터 N까지 수를 모두 큐에 넣어줌.
        }

        bw.write("<");
        for (int i=0; i<N; i++) {
            if (i != 0) {
                bw.write(", ");
            }
            for (int j=0; j<T-1; j++) { // T-1번째 요소까지는
                queue.offer(queue.poll()); // 빼서 큐의 맨 뒤에 다시 넣는다
            }
            bw.write(Integer.toString(queue.poll())); // 그 상태에서 빼면 T번째 요소를 얻을 수 있음
            bw.flush(); // 쓴 후에는 bw를 정리하자
        }
        bw.write(">");
        bw.flush();
        
        br.close();
        bw.close();
    }

}

 

로그인

 

 

작성일자: 2023-09-01