[P&B] #23 PreCodingTest

프리코딩테스트 2-3

 

5) Josephus Problem

오답 노트 코드

class Solution{
	public static int solution(int N, int K) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(i + 1);
        }

        int index = 0;
        while (list.size() != 1) {
            index = (index + K - 1) % list.size();
            list.remove(index);
        }

        int answer = list.get(0);
        return answer;
    }
}

 

문제 풀이 코멘트

index = (index + K - 1) % list.size();
list.remove(index);

이 부분은 현재 인덱스에서 K번째 앞에 있는 사람을 제외하는 역할을 한다. (index + K - 1)은 K번째 앞에 있는 사람의 인덱스를 계산하며, % list.size()를 사용하여 리스트 범위 내에서 유지합니다. 처음에는 리스트에 1부터 N까지의 숫자가 순서대로 들어있을 것이다. 그런데 한 명이 제외되고 나면, 리스트의 크기가 줄어들게 된다. 이때, 원형 모양으로 앉아있기 때문에 K번째 사람은 리스트에서 K만큼 뒤에 있는 사람이 된다. 하지만 만약 리스트의 크기를 벗어나는 인덱스라면 다시 처음으로 돌아와야 한다. 이를 고려하여 (index + K - 1) % list.size() 식을 사용한다. 이 식에서 index는 현재 사람의 인덱스를 나타내고, K - 1은 K번째 앞에 있는 사람의 간격을 나타낸다. 그리고 % list.size()는 리스트의 크기를 벗어난 경우를 처리하기 위해 리스트 크기로 나눠준다. 이렇게 함으로써 리스트의 범위 내에서 K번째 앞에 있는 사람의 인덱스를 구할 수 있게 된다. 그런 다음 해당 인덱스의 사람을 리스트에서 제거한다. 반복문이 끝나면 리스트에는 마지막으로 남은 사람만 남게 되고, 이 사람의 번호를 반환하여 문제를 해결한다.