코딩 테스트 합격자 되기 | 문제15. 요세푸스 문제

15. 요세푸스 문제

N명의 사람이 원 형태로 서 있습니다. 각 사람은 1부터 N까지 번호표를 갖고 있습니다. 그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앱니다.

 

• 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앱니다.
• 없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앱니다.

 

N과 K가 주어질 때 마지막에 살아있는 사람의 번호를 반환하는 solution() 함수를 구현해주세요

 

제약조건

N과 K는 1이상 1000이하의 자연수 입니다.

 

입출력의 예

N	K	return
5	2	3

 

내 답안

import java.util.*;


public class q2 {
    public static void main(String[] args) {
         int n = 5;
         int k = 2;
         int result = solution(n,k);
        System.out.println(result);
    }

    public static int solution(int n, int k) {
        ArrayDeque<Integer> q= new ArrayDeque<>();
        for (int i=0;i<n;i++){
            q.addLast(i+1);
        }
        while(q.size()>1){
            for(int j=0;j<k;j++){
                if(j==k-1){
                    q.pollFirst();
                    continue;
                }
                q.addLast(q.pollFirst());
            }
        }
        return q.peekFirst();

    }
}