6. 공주 구하기
<설명>
정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다.
정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은
다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.
왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N
번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시
계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그
왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시
1부터 시작하여 번호를 외친다.
이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.
예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자.
처음에는 3번 왕자가 3을 외쳐 제외된다. 이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로
제외되고 마지막까지 남게 된 7번 왕자에게 공주를 구하러갑니다.
N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.
<입력>
첫 줄에 자연수 N(5<=N<=1,000)과 K(2<=K<=9)가 주어진다.
<출력>
첫 줄에 마지막 남은 왕자의 번호를 출력합니다.
===================================================
<코드>
먼저 인원수 만큼 queue에 넣어 준 후 지정번호-1번까지 remove하고 다시 그 번호를 queue에 넣어준다. 지정 번호를 부른 왕자는 remove한다. queue의 사이즈가 1이 아닐 때까지만 이 동작을 수행하도록 한다.
import java.util.*;
class Main {
public int solution(int prince,int n) {
int answer=0;
Queue<Integer> queue=new LinkedList<>();
for(int i=1;i<=prince;i++) queue.add(i);
while(queue.size()!=1) {
for(int j=1;j<n;j++) { queue.add(queue.remove());}
queue.remove();
}
answer=queue.poll();
return answer;
}
public static void main(String[] args) {
Main main = new Main();
Scanner scan = new Scanner(System.in);
int prince=scan.nextInt();
int n=scan.nextInt();
System.out.println(main.solution(prince,n));
}
}<중요>
1) Queue<..> queue = new LinkedList<>()
- 큐
2) queue.add( )
- 삽입
3)queue.remove( )
- 제거
