[백준] 1158번 : 요세푸스 문제

📚 문제

이미지를 클릭하시면 문제 링크로 연결됩니다.

---

📝 문제 이해 및 풀이

• 사람들을 큐에 저장한다.
• K 직전까지 큐의 맨 앞을 맨 뒤로 보낸다.
• K 번째라면 제거하고 그 값을 출력한다.
• 사이즈가 1일때까지 반복하고 1이라면 그 값을 그대로 출력한다.

---

💻 소스 코드

import java.io.*;
import java.util.*;

// 5일차 (연결 리스트) - 백준 요세푸스 문제
public class day05Baek1158 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());   // n명의 사람
        int k = Integer.parseInt(st.nextToken());   // 순서대로 k번째 사람을 죽인다

        ArrayList result = new ArrayList();  // 죽이는 순서를 담을 배열

        Queue q = new LinkedList();

        // 큐에 인원 수를 담아준다.
        for (int i = 1; i <= n; i++) {
            q.offer(i);
        }

        // 큐가 한 개만 남을때까지 루프
        while(q.size() != 1){
            for (int i = 0; i < k-1; i++) { // k번째 직전까지 맨 뒤로 보낸다.
                q.offer(q.poll());
            }
            result.add(q.poll());   // k 번째를 결과를 담을 배열에 넣어주고 제거
        }

        result.add(q.poll());   // 마지막으로 남은 번호 결과에 넣어주고 제거

        System.out.print("<");
        for (int i = 0; i < result.size(); i++) {
            if(i == result.size() - 1){
                System.out.print(result.get(i));
            } else {
                System.out.print(result.get(i) + ", ");
            }
        }
        System.out.print(">");
    }
}