섹션 5. Stack, Queue(자료구조) 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. K번 전까지의 번호를 큐에서 꺼내고, 맨 뒤로 다시 넣는다.

2. K번째 번호는 큐에서 제거한다.

3. 큐의 크기가 1이 될 때까지 반복한다.

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

 

2. int 형으로 메소드를 작성한다.

 

3. for문을 사용해서 Queue에 N번까지의 번호를 넣는다.

• offer() : 순차적으로 값을 넣는다.

4. 큐에 값이 비기 전까지 돌아가는 while문을 선언한다.

 

5. for문을 사용해서 Q에서 값을 꺼내고, 꺼낸 값을 다시 넣는다.

• poll() : 가장 먼저 보관한 값 꺼내고 반환한다.
• 1부터 K까지 돌아가므로, K 바로 전의 번호까지 적용된다.
• 값을 꺼낸 후에 꺼낸 값을 다시 넣는다.

6. K 번째 값은 바로 제거한다.

 

7. 큐에 하나만 남아있다는 건 결과값임을 의미하므로 result 변수에 넣는다.

 

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.