[문제풀이] 05-08. 응급실

인프런, 자바(Java) 알고리즘 문제풀이

Stack, Queue(자료구조) - 0508. 응급실

---

🗒️ 문제

---

🎈 나의 풀이

	private static class Patient {
        private int index;
        private int warn;

        public Patient(int index, Integer warn) {
            this.index = index;
            this.warn = warn;
        }

        public int getIndex() { return this.index; }

        public int getWarn() {
            return  this.warn;
        }
    }

    private static int solution(int m, ArrayList<Integer> list) {
        int answer = 1;
        Queue<Patient> Q = new LinkedList<>();

        for(int i=0; i<list.size(); i++) {
            Q.add(new Patient(i, list.get(i)));
        }

        Collections.sort(list);
        Collections.reverse(list);

        while(!list.isEmpty()) {
            Patient p = Q.poll();
            if(p.getWarn() >= list.get(0)) {
                if(p.getIndex() == m) return answer;
                else list.remove(0);
                answer++;
            } else {
                Q.add(p);
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<Integer> list = new ArrayList<>();

        for(int i=0; i<n; i++) {
            list.add(sc.nextInt());
        }

        System.out.println(solution(m, list));

    }

---

🖍️ 강의 풀이

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

  class Main {	
      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;
      }

      public static void main(String[] args) throws IOException{
          Main T = new Main();
          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));	
      }
  }

---

💬 짚어가기

해당 문제는 Queue를 이용하여 풀 수 있다. 나의 풀이에서는 환자의 정보를 저장할 수 있도록
Patient 클래스를 생성했다. 이는 환자의 접수 번호와 위험도를 인스턴스 변수로 갖는다.

우선 접수 순서대로 ArrayList에 보관하였다. 요소 삭제와 정렬을 용이하게 하기위해 해당
자료구조를 선택했다.

다음 List를 순회하며 인덱스는 접수 번호로, 값은 위험도로하여 Patient 객체를 생성하였고
생성된 객체는 차례되로 큐에 보관하였다. 그 다음 List를 내림차순 정렬하여 환자들의 위험도를
높은 순으로 보관하였다.

이제 큐를 순회하며 해당 환자의 위험도가 List의 가장 높은 위험도와 일치하는지 판별하였다.

• 결과가 거짓이라면 해당 환자를 다시 큐에 넣는다.
• 결과가 참인 경우 List의 해당 위험도를 제거하고, 환자 순번을 증가시킨다.

최종적으로 관심 대상의 환자가 등장하고 위험도가 일치하는 경우 순번을 반환하여 문제를 해결한다.

강의에서는 마찬가지로 환자의 정보를 보관할 수 있는 클래스를 생성하고, 환자들을 큐에 보관한다.
다음 큐에서 한명을 꺼내오고, 큐를 순회하며 나머지 환자들과의 위험도를 비교한다.

만약 위험도가 앞서는 환자가 있다면 해당 환자는 다시 큐에 넣도록 하고, 그렇지 않은 경우 해당
환자는 큐에서 제거되고 순번을 증가시킨다.

관심 대상의 환자가 나머지 환자들보다 위험도가 앞서는 순간에 순번을 반환하여 문제를 해결하나.