섹션 5. Stack, Queue(자료구조) 8. 응급실

문제

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

입력

• 첫 줄에 자연수 N(5<=N<=100)과 M(0<=M<N) 주어집니다.
• 두 번째 줄에 접수한 순서대로 환자의 위험도(50<=위험도<=100)가 주어집니다.
• 위험도는 값이 높을 수록 더 위험하다는 뜻입니다. 같은 값의 위험도가 존재할 수 있습니다.

출력

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

입출력 예제

---

풀이방식

이번 문제는 Queue(큐), 배열, 클래스를 사용하여 푸는 문제이다.

---

설계과정

1. 대기 목록 상의 환자 번호와 위험도를 큐에 넣는다.

2. 맨 처음 환자를 큐에서 꺼내서 임의의 변수에 넣는다.

3. 대기 목록에서 처음 환자보다 위험도가 높은 환자가 있는지  확인한다.

4. 높은 환자가 있으면 처음 환자의 위험도를 큐 맨 뒤에 넣는다.

5. 만약 처음 환자의 위험도가 가장 높다면 결과값을 누적한다.

6. M 번째 환자가 위험도가 가장 높게 되면, 누적된 결과값을 리턴한다.

---

풀이과정

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

 

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

 

3. Person 클래스를 만들고, 객체를 생성하여 초기화한다.

• 큐에 값을 넣을 때에 대기 목록 상의 환자 번호와 위험도를 같이 넣기 위해 클래스를 생성한다.
• 이 때 클래스에는 환자 번호를 의미하는 id 와 위험도를 의미하는 priority 객체를 선언하고 초기화한다. 
• id() : 대기 목록 상의 환자 번호
• priority() : 위험도

4. 클래스 객체형을 가지는 Q를 선언하고, 값을 넣는다. 

• offer() : 순차적으로 값을 넣는다.
• 예제 상으로 Person(i, arr[i]) 에는 (0, 60), (1, 50), (2, 70), (3, 80), (4, 90) 이라는 값이 들어가게 된다.
• 즉 아래 이미지와 같이 Q에 값이 들어간다.

5. 큐에 값이 없을 때까지 도는 while 문을 선언한다.

• isEmpty() : 값이 비었는지 확인하여 true / false로 리턴한다.

6. 큐에 들어간 맨 처음 환자를 꺼내서 임의의 변수 tmp에 저장한다.

• poll() : 가장 먼저 보관한 값을 꺼내고 반환한다.
• tmp에는 id = 0 / priority = 60 이 들어간다.

7. x가 Q보다 위험도가 크면 큐에 tmp 값을 넣고 break를 통해 끝낸다.

• 해당 환자가 위험도가 적어 진료를 볼 수 없음이 확인되면 더 탐색할 필요가 없으므로 break를 통해 끝낸다.
• 해당 과정을 반복하면 아래 이미지와 같은 결과를 볼 수 있다. (10번을 수행한 결과이다.)

8. 환자가 진료를 받을 수 있으면 결과에 1씩 누적한다.

• tmp가 null이 아니라는 것은 즉 진료를 받을 수 있는 환자라는 의미이다.
• 앞에 환자가 진료를 받은 횟수만큼 누적하도록 result를 1씩 누적한다.

9. M 번째 환자가 진료를 받을 수 있으면 누적된 결과값을 출력한다.

---

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