[Ch.05 - StackQueue] 08. 응급실 #

8. 응급실

 

설명

메디컬 병원 응급실에는 의사가 한 명밖에 없습니다.

응급실은 환자가 도착한 순서대로 진료를 합니다. 하지만 위험도가 높은 환자는 빨리 응급조치를 의사가 해야 합니다.

이런 문제를 보완하기 위해 응급실은 다음과 같은 방법으로 환자의 진료순서를 정합니다.

• 환자가 접수한 순서대로의 목록에서 제일 앞에 있는 환자목록을 꺼냅니다.

• 나머지 대기 목록에서 꺼낸 환자 보다 위험도가 높은 환자가 존재하면 대기목록 제일 뒤로 다시 넣습니다. 그렇지 않으면 진료를 받습니다.

즉 대기목록에 자기 보다 위험도가 높은 환자가 없을 때 자신이 진료를 받는 구조입니다.

현재 N명의 환자가 대기목록에 있습니다.

N명의 대기목록 순서의 환자 위험도가 주어지면, 대기목록상의 M번째 환자는 몇 번째로 진료를 받는지 출력하는 프로그램을 작성하세요.

대기목록상의 M번째는 대기목록의 제일 처음 환자를 0번째로 간주하여 표현한 것입니다.

입력

첫 줄에 자연수 N(5<=N<=100)과 M(0<=M<N) 주어집니다.

두 번째 줄에 접수한 순서대로 환자의 위험도(50<=위험도<=100)가 주어집니다.

위험도는 값이 높을 수록 더 위험하다는 뜻입니다. 같은 값의 위험도가 존재할 수 있습니다.

출력

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

 

 

예시 입력 1 

5 2
60 50 70 80 90

예시 출력 1

3

예시 입력 2 

6 3
70 60 90 60 60 60

예시 출력 2

4

---

배열에서 내림차순 정렬

-> Integer [] 로 배열을 선언 한 후,

Arrays.sort(arr, Collections.reverseOrder());

 

다른 자료구조의 경우

Collections.sort(queue, Collections.reverseOrder());

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
//배열 reverseOrder

public class asdf {
	public int solution(Integer[] arr, int m) {
		Queue<Integer> q = new LinkedList<>();
		int answer = 1;
		// Arrays.sort(arr);
		int tmp = arr[m];
		Arrays.sort(arr, Collections.reverseOrder());
		for (int i = 0; i < arr.length; i++) {
			q.offer(arr[i]);
			if (tmp == arr[i]) {
				answer = i;
			}
		}

		return answer + 1;
	}

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

	}
}

-> 테스트 케이스 중 틀린 경우 존재

 

이유 : 같은 응급도가 존재할 경우 정렬을 한다면, 순서를 파악하기 어렵다.

 

• 나머지 대기 목록에서 꺼낸 환자 보다 위험도가 높은 환자가 존재하면 대기목록 제일 뒤로 다시 넣습니다. 그렇지 않으면 진료를 받습니다.

 

-> 정렬을 하지 않고, 큐를 돌면서 더 응급도가 높은 경우 찾기

-> 응급도를 따져서, 응급도가 더 높은 다른 환자가 있으면 빼서 다시 넣기

 

 

 

import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
//배열 reverseOrder

public class asdf2 {
	public int solution(LinkedHashMap<Integer, Integer> map, int m) {
		Queue<Integer> q = new LinkedList<>();
		int answer = 1;
		List<Map.Entry<Integer, Integer>> entryList = new LinkedList<>(map.entrySet());
		entryList.sort(Map.Entry.comparingByValue(Collections.reverseOrder()));

//		entryList.sort(new Comparator<Map.Entry<Integer, Integer>>() {
//		    @Override
//		    public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
//			return o1.getValue() - o2.getValue();
//		    }
//		});
		HashMap<Integer, Integer> temp = new LinkedHashMap<>();

		for (Map.Entry<Integer, Integer> aa : entryList) {
			temp.put(aa.getKey(), aa.getValue());
		}
		Set<Integer> keys = temp.keySet();
		 
		List<Integer> listKeys = new LinkedList<Integer>( keys );
		answer=listKeys.indexOf(m);
		return answer+1;
	}

	public static void main(String[] args) {
		asdf2 T = new asdf2();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
		for (int i = 0; i < n; i++) {
			map.put(i, kb.nextInt());
		}
		System.out.println(T.solution(map, m));

	}
}

LinkedHashset value기준 정렬

List<Map.Entry<Integer, Integer>> entryList = new LinkedList<>(map.entrySet());
entryList.sort(Map.Entry.comparingByValue(Collections.reverseOrder()));

 

정렬 후 다시 map으로 넣기

HashMap<Integer, Integer> temp = new LinkedHashMap<>();
for (Map.Entry<Integer, Integer> aa : entryList) {
temp.put(aa.getKey(), aa.getValue());}
Set<Integer> keys = temp.keySet()

 

정렬한 LinkedHashMap의 키로 Index 찾기

Set<Integer> keys = temp.keySet();
List<Integer> listKeys = new LinkedList<Integer>( keys );
answer=listKeys.indexOf(m);
return answer+1;

 

-> entrySet, keySet, valueSet 모두 set 자료구조로 만들어진다.

---

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 Main {
	// # 응급실
	// 환자 도착 순 진료, 위험도 높은 환자 먼저
	// 대기목록과 비교해 위험도 높은 환자가 없으면 진료

	// N명 대기목록 순서 환자 위험도 주어지면, M번째 환자는 몇번째로 진료받는지 자것ㅇ
	// M번째는 0번째부터 센다
	// 첫 줄에 대기환자 N 5이상, 대기 목록 순서 M
	// 두번째 줄에 접수 순 위험도 50이상 100이하 [같은 값 존재 가능]

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int k = kb.nextInt();
		int [] arr = new int[n];
		for(int i=0; i<n;i++) {
			arr[i] = kb.nextInt();
		}
		
		System.out.println(T.solution(n,k, arr));
		kb.close();
	}
	
	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.priority>tmp.priority) {
					Q.offer(tmp);
					tmp=null;
					break;
				}
			}
			if(tmp!=null) {
				answer++;
				if(tmp.id==m)
					return answer;
			}
		}
		return answer;
	}
}

 

일단 큐에서 하나를 빼서, 하나 뺀 사람과 큐를 반복하면서 다른 대기 사람과 비교 [큐가 빌때까지 반복]

-> 모두 정렬이 된 경우 offer가 발생하지 않으므로, 모두 정렬이 되고 나서 한바퀴 돌 경우 = 큐가 빌때 

 

큐를 이용한 생성자

Queue<Person> Q = new LinkedList<>();

 

큐를 반복해서 방문

for(Person x:Q)

 

클래스의 경우 초기화할때는 null로 초기화

tmp=null;

 

해당 환자가 응급도가 높으면, if(tmp!=null)

tmp.id==m -> id는 바뀌지 않으므로

 

---

1. 하나하나마다 while문을 돌려서 위급도를 비교한다. -> 발견시 뒤에 넣고 continue;

2. 위험도가 더 높은 환자가 없으면 인덱스 체크 하고, answer++;

import java.util.*;
class Pat{
  public int index, value;
  Pat(int index, int value){
    this.index=index;
    this.value=value;
  }
}
public class Main {
  
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int[] arr= new int[n];
    for(int i=0;i<n;i++) arr[i]=in.nextInt();
    System.out.println(Solution(n, m, arr));
  }
  private static int Solution(int n, int m, int[]arr){
    Queue<Pat> q = new LinkedList<>();
    int answer=1;
    for(int i=0;i<n; i++){
      Pat pat= new Pat(i, arr[i]);
      q.offer(pat);
    }
    e: while(!q.isEmpty()){
      Pat pat=q.poll();
      for(Pat tmp : q){
        if(pat.value<tmp.value) {
          q.offer(pat);
          continue e;
        }
      }
      if(pat.index==m) return answer;
      answer++;
    }
    
    return answer;
  }
}