공주 구하기

정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다.

정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.

왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다.

그리고 1번 왕자부터 N번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다.

그리고 1번 왕자부터 시계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다.

한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다.

그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다.

이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.

 

큐를 이용해서 푸는 문제 

큐 선언은 Queue queue = new LinkedList<>(); 형태로 링크드리스트로 선언하고 

offer와 poll 으로 삽입, 삭제 contain으로 해당 원소가 큐에 있는지 확인할 수 있다

 

큐를 순회하면서 해당 숫자의 차례가 되면 poll 아니면 그 숫자를 offer해서 큐에 추가하는 방식으로 큐 크기를 줄여나가면서 마지막 숫자가 남을때까지 계속 진행했다

 

import java.util.*;
public class Main {
    public int Solution(int n, int k){
        Queue<Integer> queue = new LinkedList<>();
        int tmp = 0;

        for(int i =1; i <= n; i++){
            queue.offer(i);
        }

        while (queue.size() != 1){
            tmp = tmp % k;
            if(tmp == k-1) queue.poll();
            else queue.offer(queue.poll());
            tmp++;
        }
        return queue.poll();
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();

        System.out.println(T.Solution(n,k));
    }
}

 

 

 

큐 - offer poll contain

큐 선언 - Queue<Integer> queue = new LinkedList<>();

앞에서부터 돌면서 해당 숫자가 되면 poll 아니면 poll한 것을 offer로 더해줌