백준 1158 요세푸스 문제

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

public class Yosepus {
    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());
        StringBuilder sb = new StringBuilder();
        sb.append("<");
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(i+1);
        }
        int index = -1;
        while (!list.isEmpty()){
            index = (index+K)%list.size();
            if(list.size()==1) {
                sb.append(list.get(index)).append(">");
                break;
            }
            sb.append(list.get(index)).append(", ");
            list.remove(list.get(index));
            index -=1;
        }
        System.out.println(sb);
    }
}

풀이방법

이문제는 리스트에서 하나씩 숫자를 제거해가며 푼다는 설계를 하는것이 핵심이다.
또한 탐색을 원형으로 돌면서 하므로 % 연산 사용을 계획한다.

1. while문을 반복하면서 index = (index+K-1)%list.size();해준다.
   list인덱스0에 1부터 담겨있으므로 처음 index는 -1로 설정한다.
   list를 넘어가면 다시 처음으로 돌아간다.
2. 인덱스에 해당하는 리스트값을 stringbuilder에 추가 시킨다.
3. 리스트에서 그값을 제거한다.
4. 값을 제거 했으므로 인덱스도 -1해준다.
5. 리스트에 마지막값을 stringbuilder에 추가시킬 때는 >문자를 포함시킨다.

후기

핵심은 잘 파악했는데, 구현하는것에서 좀 헤맸다.
배열로도 시도했었는데 그러면 체크해야 할것이 많아져서 더 복잡한거 같다.