[JAVA]BOJ 1158, 요제푸스 문제

드디어 List를 사용한 문제이다. 문제를 푸는 여러 방법이 있겠지만, 나는 ArrayList를 사용했다.

 

풀이방법

k번째 값을 빼준다. 다음은 k번째부터 +k번째 값을 또 뺀다.. 손으로 풀면 규칙이 보인다. 지속적으로 k - 1을 더해주고, 더한 값이 전체 배열 사이즈보다 큰 경우 '% 사이즈' 를 한 후 +k번째 값을 뺀다.. 그렇게 계속 빼다가 배열에 남은 값이 없으면 끝이다.

---

아래는 전체 코드이다.

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

public class BOJ1158 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> list = new ArrayList<>();
        int N, K, i;

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        // arrayList 초기화
        for (i=1;i<=N;i++)
            list.add(i);

        System.out.print("<");
        i = 0;
        while(!list.isEmpty()){
            i += (K - 1); // k - 1 을 더해준다.
            
            if(i < list.size()) // 전체 크기보다 작은 경우는
                System.out.print(list.remove(i)); // 그냥 빼고
            else{ // 전체 크기보다 큰 경우는
                i %= list.size(); // 나머지 연산 후
                System.out.print(list.remove(i)); // 뺀다.
            }

            if(list.size() >= 1) // 출력조건: 마지막 값 빼고 , 를 출력
                System.out.print(", "); 
        }
        System.out.print(">");
    }
}