섹션 5. Stack, Queue - 6. 공주 구하기

📌 문제 설명

정보 왕국의 왕자는 공주를 구하러 가기 위해 순서를 정해야 합니다.
왕자들이 원형으로 앉아 있고, 숫자를 외쳐가며 특정 숫자를 외친 왕자는 제외됩니다.
마지막까지 남은 왕자가 공주를 구하러 가게 됩니다.

---

📝 입력 & 출력

입력

• 첫 줄에 자연수 N(5 ≤ N ≤ 1,000)과 K(2 ≤ K ≤ 9)가 주어집니다.
• N은 왕자의 수, K는 제외 조건 숫자입니다.

출력

• 마지막까지 남은 왕자의 번호 출력

---

🔹 예제 입력 & 출력

예제 입력 1

8 3

 

예제 출력 1

 

7

---

💡 해결 방법

이 문제는 Queue(큐) 자료구조를 활용한 시뮬레이션 문제입니다.

1. 1번부터 N번까지 왕자 번호를 큐에 넣습니다.
2. K-1명은 다시 큐의 뒤로 보내고, K번째는 제거합니다.
3. 큐의 크기가 1이 될 때까지 반복하면, 마지막 남은 왕자가 정답입니다.

이 방식은 요세푸스 문제(Josephus Problem) 와 동일한 원리입니다.

---

💻 코드 구현 (Java)

package partStackQueue;

import java.util.*;

public class Problem6 {
	public int solution(int n, int k) {
		int result = 0;
		Queue<Integer> Q = new LinkedList<>();
		for (int i = 1; i <= n; i++) Q.offer(i);

		while (!Q.isEmpty()) {
			for (int i = 1; i < k; i++) Q.offer(Q.poll()); // 앞에서 꺼내서 뒤로 보냄
			Q.poll(); // k번째 왕자 제거
			if (Q.size() == 1) result = Q.poll(); // 마지막 남은 왕자
		}
		return result;
	}

	public static void main(String[] args) {
		Problem6 T = new Problem6();
		Scanner kb = new Scanner(System.in);
		System.out.print(T.solution(kb.nextInt(), kb.nextInt()));
		kb.close();
	}
}

---

📖 코드 설명

Queue<Integer> Q = new LinkedList<>();
for (int i = 1; i <= n; i++) Q.offer(i);

• 1번부터 N번까지 왕자를 큐에 삽입

for (int i = 1; i < k; i++) Q.offer(Q.poll());

• K번째가 아닐 때까지 앞에서 빼서 다시 뒤로 삽입 → 순환 구조

Q.poll();

• K번째 왕자 제거

if (Q.size() == 1) result = Q.poll();

• 마지막 남은 왕자 추출

---

⏳ 시간 복잡도 분석

• 전체 왕자 수가 N이고, 각 단계마다 최대 K-1번 큐 삽입·삭제 → O(N * K)
• K는 최대 9로 상수 취급 → 전체 시간 복잡도는 O(N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런