[백준 / 실버5] 11866 : 요세푸스 문제 0 (JAVA)

문제

---

풀이 방법

• Queue
  • k번째 수가 되기 직전까지 맨 앞의 원소를 꺼내오고(poll) 꺼내온 원소들을 맨 뒤로 넣는다.(offer)
  • k번째 수는 꺼내서(poll) 출력한다.
• List
  • k값을 매번 k씩 증가시켜 해당 원소를 삭제하면서 그 값을 출력한다.
  • 이때, 리스트의 시작은 0부터 이므로 k-1이며 참조하려는 인덱스가 참조 범위보다 커질 수 있으므로 현재 리스트의 크기를 나눈 나머지 값으로 증가시켜야 한다.

---

코드

👇🏻 Queue

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

public class Main {
    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());
        int k = Integer.parseInt(st.nextToken());

        Queue<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();

        for(int i = 1; i<=n; i++){
            q.add(i);
        }

        sb.append("<");
        while(q.size()>1){
            for(int i=0; i<k-1; i++){
                int val = q.poll();
                q.offer(val);
            }
            sb.append(q.poll()).append(", ");
        }

        sb.append(q.poll()).append(">");
        System.out.println(sb);


    }
}

👇🏻 List

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int index = 0;
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }

        sb.append("<");
        while (list.size() > 1) {
            index = (index + (k - 1)) % list.size();
            sb.append(list.remove(index)).append(", ");

        }
        sb.append(list.remove(index)).append(">");

        System.out.println(sb);
    }
}