[백준] 11866 - 요세푸스 문제 0

처음에는 그냥 단순히 큐로 구현했다. 역시나 풀리긴 하지만 시간 / 메모리를 좀 먹는 편.

 

아래는 큐가 아닌 LinkedList로 구현한 방법이다.

idx가 움직이는 것을 다음과 같이 설명할 수 있다.

1. idx에 처음에 K-1만큼 더해준다. 우선 배열은 하나가 사라지면, 그 다음 걸 가리키게 되므로 한칸 내려서 더해준다. -1하지 않으면 원래 탐색 대상은 넘어가 버린다.

2. %= 연산을 통해 마치 실제로 큐에 계속 데이터를 넣는 것처럼 구현할 수 있다.

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        List<Integer> Q = new LinkedList<>();

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

        for(int i = 1; i <= N; i++) {
            Q.add(i);
        }

        int idx = 0;
        sb.append("<");
        while(!Q.isEmpty()) {
            idx += K-1;
            if(idx >= Q.size()) {
                idx %= Q.size();
            }
            if(Q.size() != 1) {
                sb.append(Q.remove(idx) + ", ");
            } else
                sb.append(Q.remove(idx) + ">");
        }
        System.out.println(sb);
    }
}