[Java] 프로그래머스 코딩테스트 - 요세푸스 문제 (큐)

프로그래머스 코딩테스트 - 요세푸스 문제

 

 문제 설명

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

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

 

 제한 조건

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

 

 입출력 예

N	K	return
5	2	3

 

 코드

import java.util.*;

public class Solution {
    public int solution(int []arr) {
        int N = 5;
        int K = 2;
        
        // 큐를 사용해도 되지만, 직관적인 이해를 위하여 덱을 사용함.
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        
        if(N == 1) return 1;
        
        for(int i = 1; i <= N; i ++) {
            deque.addLast(i);
        }
        
        // 선입 선출
        while(deque.size() > 1) {
            for(int i = 0; i < K - 1; i ++) {
                deque.addLast(deque.pollFirst());
            }
            
            deque.pollFirst();
        }
        return deque.pollFirst();
    }
}