[Algorithm/Java] 알고리즘 자바 응급실 (코딩테스트, Stack, Queue, 스택, 큐, 자료구조, 위급한 환자 우선순위)

---

1. 문제 설명

• 설명
  메디컬 병원 응급실에는 의사가 한 명밖에 없습니다.
  응급실은 환자가 도착한 순서대로 진료를 합니다. 하지만 위험도가 높은 환자는 빨리 응급조치를 의사가 해야 합니다.
  이런 문제를 보완하기 위해 응급실은 다음과 같은 방법으로 환자의 진료순서를 정합니다.
  • 환자가 접수한 순서대로의 목록에서 제일 앞에 있는 환자목록을 꺼냅니다.
  • 나머지 대기 목록에서 꺼낸 환자 보다 위험도가 높은 환자가 존재하면 대기목록 제일 뒤로 다시 넣습니다. 그렇지 않으면 진료를 받습니다.
  즉 대기목록에 자기 보다 위험도가 높은 환자가 없을 때 자신이 진료를 받는 구조입니다.
  현재 N명의 환자가 대기목록에 있습니다.
  N명의 대기목록 순서의 환자 위험도가 주어지면, 대기목록상의 M번째 환자는 몇 번째로 진료를 받는지 출력하는 프로그램을 작성하세요.
  대기목록상의 M번째는 대기목록의 제일 처음 환자를 0번째로 간주하여 표현한 것입니다.
• 입력
  첫 줄에 자연수 N(5<=N<=100)과 M(0<=M<N) 주어집니다.
  두 번째 줄에 접수한 순서대로 환자의 위험도(50<=위험도<=100)가 주어집니다.
  위험도는 값이 높을 수록 더 위험하다는 뜻입니다. 같은 값의 위험도가 존재할 수 있습니다.
• 출력
  M번째 환자의 몇 번째로 진료받는지 출력하세요.

 

2. 문제 코드 및 풀이 설명

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

// 환자 클래스
class Person {
  int id;
  int risk;

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

public class EmergencyRoom {
  public static void main(String[] args) {
    EmergencyRoom T = new EmergencyRoom();
    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.println(T.solution(n, m, arr));
  }

  // 해결방법
  // 환자의 처음 순서와 위험도를 가진 객체로 큐 생성
  // 처음 환자를 큐를 돌며 위험도가 더 높은 환자가 있는지 확인
  // 있다면 넘기고 아니면 제거, 이때 제거하는 환자의 처음 순서가 찾아야하는 환자라면 리턴
  // 아니라면 같은 과정 반복
  public int solution(int n, int m, int[] arr) {
    int answer = 0;
    Queue<Person> Q = new LinkedList<>();

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

    while (!Q.isEmpty()) {
      Person tmp = Q.poll(); // 확인하기 위해 하나를 꺼낸다
      for (Person x : Q) {
        if (x.risk > tmp.risk) { // 확인하는 환자보다 더 위험한 환자가 있다면
          Q.offer(tmp); // 환자를 맨 뒤로 보낸다
          tmp = null; // tmp를 비워서 맨 뒤로 보냈음을 확인
          break;
        }
      }
      if (tmp != null) { // 맨 뒤로 보내지 않았다면
        answer++;
        if (tmp.id == m) return answer; // 그 사람이 m번째 사람이었다면 리턴
      }
    }
    return answer;
  }
}

 

3. 출력 예시

입력
5 2
60 50 70 80 90

출력
3

 

 

---

위의 내용은 인프런에서 수강할 수 있는 김태원님의 자바 알고리즘 문제풀이 강의를 바탕으로 공부한 내용을 정리한 내용입니다!

https://inf.run/iAi6

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