섹션 5. Stack, Queue - 8. 응급실

📌 문제 설명

응급실에는 환자가 도착한 순서대로 진료를 받지만 위험도가 더 높은 환자가 우선됩니다.
다음 규칙에 따라 진료 순서를 결정합니다:

• 환자를 접수 순서대로 큐에 저장
• 가장 앞에 있는 환자보다 더 높은 위험도의 환자가 있다면 해당 환자를 큐 뒤로 보냄
• 그렇지 않다면 진료

M번째 환자가 몇 번째로 진료받는지 출력하세요.

---

📝 입력 & 출력

입력

• 첫 줄: N(환자 수), M(목표 환자 위치)
• 둘째 줄: N명의 환자의 위험도 (접수 순서대로)

출력

• M번째 환자의 진료 순서 출력

---

🔹 예제 입력 & 출력

예제 입력 1

5 2
60 50 70 80 90

 

예제 출력 1

 

3

 

예제 입력 2

 

6 3
70 60 90 60 60 60

 

예제 출력 2

 

4

---

💡 해결 방법

• 환자를 객체로 만들어서 id(접수 순서)와 priority(위험도)를 함께 저장
• 큐(Queue) 를 이용해 시뮬레이션 수행
• 큐의 맨 앞 환자보다 더 높은 위험도가 뒤에 있으면 → 다시 큐 뒤로 보냄
• 그렇지 않으면 진료
• M번째 환자가 진료 받을 차례가 되면 진료 순서 반환

---

💻 코드 구현 (Java)

package partStackQueue;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Person {
	int id;
	int priority;
	public Person(int id, int priority) {
		this.id = id;
		this.priority = priority;
	}
}

public class Problem8 {
	public int solution(int n, int m, int[] arr) {
		int result = 1;
		Queue<Person> Q = new LinkedList<>();

		for (int i = 0; i < n; i++) {
			Q.offer(new Person(i, arr[i]));
		}
		
		while (!Q.isEmpty()) {
			Person current = Q.poll();
			boolean hasHigherPriority = false;
			
			for (Person other : Q) {
				if (other.priority > current.priority) {
					hasHigherPriority = true;
					break;
				}
			}
			
			if (hasHigherPriority) {
				Q.offer(current);
			} else {
				if (current.id == m) return result;
				result++;
			}
		}
		return result;
	}

	public static void main(String[] args) {
		Problem8 T = new Problem8();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) arr[i] = kb.nextInt();
		System.out.print(T.solution(n, m, arr));
		kb.close();
	}
}

---

📖 코드 설명

class Person {
	int id;
	int priority;
}

• id: 환자의 고유한 접수 번호
• priority: 환자의 위험도

Queue<Person> Q = new LinkedList<>();
for (int i = 0; i < n; i++) {
	Q.offer(new Person(i, arr[i]));
}

• 환자 정보를 큐에 저장

Person current = Q.poll();
for (Person other : Q) {
	if (other.priority > current.priority) {
		Q.offer(current);
		continue outer;
	}
}

• 현재 환자보다 더 위험한 환자가 뒤에 있다면 다시 큐 뒤로 보냄

Person current = Q.poll();
for (Person other : Q) {
	if (other.priority > current.priority) {
		Q.offer(current);
		continue outer;
	}
}

• M번째 환자가 진료 받을 차례면 진료 순서를 반환

---

⏳ 시간 복잡도 분석

• 각 환자에 대해 최대 N번 비교할 수 있으므로 → O(N²)
• N이 최대 100이므로 시간 내 충분히 해결 가능

---

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

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

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