[백준] 1158번 - 요세푸스 문제

💎 문제 링크

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

📝 문제

 

✍🏻 입력 & 출력

 

🤔 풀기 전에 생각하기

ArrayList를 할당하고 몇 번째의 숫자 인지, 인덱스 개념을 잘 생각해야 한다.

원하는 값을 찾으면 list.remove(Integer.valueOf("원하는 값"); 을 이용해 list에서 값을 지워주고 새로운 배열에 넣어준다.

 

remove메소드를 사용하면 list에서의 인덱스는 자동으로 하나씩 줄여지기 때문에 입력받은 K도 하나씩 줄여줘야 한다.

 

인덱스를 늘리다가 전체 사이즈를 넘어가게 되면 다시 처음으로 돌아올 수 있게 나머지 연산 활용

 

✨ 풀이

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int[] josep = new int[n]; // 요세푸스 순열을 담을 배열

        // 1 부터 n 까지의 정수 list 에 삽입
        for (int i = 0; i < n; i++) {
            list.add(i+1);
        }
        k--; // k는 몇 번째 인지를 의미하고 index 는 0부터 시작하기 때문에 하나 줄이고 시작

        int index = 0;
        int i = 0; // 요세푸스 배열 인덱스 관리 i
        while (list.size() > 0) {
            index = (index + k) % list.size();
            /*
             * index가 list의 크기보다 커지면 다시 처음으로 돌아와야 하기 때문에 %연산을 이용
             * list.remove()를 사용하면 알아서 크기가 하나 줄기 때문에
             * 처음 입력받은 k보다 하나 줄여서 사용한다.
             */
            josep[i] = list.get(index); // 요세푸스 배열 하나씩 채우기
            list.remove(Integer.valueOf(josep[i])); // Integer.valueOf()로 찾은 값 지우기

            i++; // 요세푸스 배열 인덱스 증가
        }

        System.out.print("<");
        for (int j = 0; j < josep.length; j++) {
            System.out.print(josep[j]);
            if (j != josep.length-1) {
                System.out.print(", ");
            }
        }
        System.out.println(">");
    }
}