요세푸스 문제 0

제출코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Deque<Integer> queue = new ArrayDeque<>();
        List<Integer> answer = new ArrayList<>();

        // 숫자를 순서대로 Deque의 끝에 추가
        for (int i = 1; i <= N; i++) {
            queue.offerLast(i); // 변경된 부분
        }

        while (queue.size() > 0) {
            for (int i = 1; i < K; i++) { // K가 3이면 2번만 옮김
          // Deque의 앞쪽에서 요소를 제거하고 다시 끝에 추가
                int a = queue.pollFirst(); 
                queue.offerLast(a); 
            }
            int b = queue.pollFirst(); 
            answer.add(b);
        }

        StringBuilder sb = new StringBuilder();
        sb.append("<");
        for (int i = 0; i < answer.size(); i++) {
            if (i == answer.size() - 1) {
                sb.append(answer.get(i));
            } else {
                sb.append(answer.get(i)).append(", ");
            }
        }
        sb.append(">");

        bw.write(sb.toString());

        bw.flush();
        bw.close();
        br.close();
    }
}

배운점

1) queue에 1~5를 offer를 하면 [5,4,3,2,1] 이 아니라 [1,2,3,4,5]다. 완전 착각하고 있었다!
queue는 어렵게 생각할게 없다. 그냥 줄서기만 떠올리자!!

public static void main(String[] args) throws IOException {
    Queue<Integer> queue = new ArrayDeque();

    for (int i = 1; i <= 5; i++) {
        queue.offer(i);
    }
    System.out.println("queue = " + queue);
    // [1,2,3,4,5]
    

    queue.poll();
    System.out.println("queue = " + queue);
    [2,3,4,5]
}

2) deque 특징 (은근 안외워짐)

• offerLast()는 deque의 마지막 부분, 즉 오른쪽에 순서대로 값들을 넣는것이다.
  Last라 그런지 반대로 작동할 것 같지만, 그냥 offer()와 동일하다.
  마찬가지로 1,2,를 offerLast() 하면 deque의 마지막 부분에 들어가는 것이다.

• 단, 다른 함수들 (like pollFirst())는 말그대로 맨 첫번째 요소를 삭제하는 것이므로 어렵게 생각하지 않아도 된다. 헷갈리지 말자~
  `