자바 알고리즘 문제 풀이 입문. ch05. Stack, Queue (자료구조) : 응급실

 

https://hyejin.tistory.com/1238

자바 알고리즘 문제 풀이 입문. ch05. Stack, Queue (자료구조) : 교육과정설계

-> 이전 문제 풀이 

 

 

설명

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

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

 

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

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

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

 

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

 

현재 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

 

 

 

문제 풀이 1

public int solution(int n, int m, int[] arr)
{
   int answer = 0;
   Queue<Patient> queue = new LinkedList<>();
   
   Patient mPatient = new Patient(arr[m], m);
   for (int i = 0; i < arr.length; i++)
   {
      queue.offer(new Patient(arr[i], i));
   }
   
   int cnt = 0;
   while (true)
   {
      int max = 0;
      for (Patient patient : queue)
      {
         if (patient.getRisk() > max) {
            max = patient.getRisk();
         }
      }
      
      if (queue.peek().getRisk() >= max) {
         if (queue.peek().equals(mPatient)) {
            cnt++;
            break;
         }else
         {
            cnt ++;
            queue.poll();
         }
      } else {
         queue.offer(queue.poll());
      }
   }
   
   
   return cnt;
}

class Patient
{
   int risk;
   int order;
   
   public Patient()
   {
   }
   
   public Patient(int risk, int order)
   {
      this.risk = risk;
      this.order = order;
   }
   
   public int getRisk()
   {
      return risk;
   }
   
   public int getOrder()
   {
      return order;
   }
   
   @Override
   public boolean equals(Object o)
   {
      if (this == o)
         return true;
      if (o == null || getClass() != o.getClass())
         return false;
      Patient patient = (Patient) o;
      return risk == patient.risk && order == patient.order;
   }
   
   @Override
   public int hashCode()
   {
      return Objects.hash(risk, order);
   }
}

 

👩‍💻 : 사실 이 문제를 어떻게 풀지 계속 고민하다가... 구글링을 했는데 객체를 하나 만들어서 Queue에 넣는 다는 힌트를 보고, 거기까지만 본 다음엔 내가 직접 풀었다 ! (객체를 생성할 생각을 하지 못했었다ㅠㅠ) 

 

암튼 Patient 라는 객체를 하나 만들고, risk가 위험도, order는 접수한 순서를 담도록 했다. 

그 다음 생성자를 만들어주고, 객체 비교를 위해서 equals를 오버라이딩해서 id와 order가 같으면 같은 객체로 인식하도록 했다. 

 

M번째 환자가 언제 진료받는지 알기 위해서 M 번째 환자를 미리 mPatient로 만들어줬다. 

그러고 이제 문제를 푸는데 Patient를 담는 Queue를 하나 만들고, 그 다음 queue에 위험도와 순서를 담아 Patent를 만들고 offer 해줬다. 

그 다음 while 무한 반복문을 만든 다음, queue를 반복문으로 돌면서 max 값 즉, 위험도가 가장 높은 값을 구하고, 그 다음, queue에서 peek 한 값이 max보다 크면 cnt 값을 +1 만 해주고, queue에서 poll 한다. 

그리고 만약 peek한 값이 max 보다 작으면 다시 queue에 넣어줘야 하기 때문에 queue에서 poll 한 값을 다시 queue에 offer 해줬다.

마지막으로  peek한 값이 max 랑 같을 때, queue.peek한 Patient가 mPatient랑 같은지 equals 비교를 통해 확인하고 risk와 order가 모두 같은 경우에는 cnt 의 값을 +1 해주고, break 을 통해 while문에서 벗어난 다음 cnt 값을 리턴해주면 된다. 

 

 

 

 

 

문제 풀이 2

public int solution2(int n, int m, int[] arr)
{
   int answer = 0;
   Queue<Person> queue = new LinkedList<>();
   for (int i = 0; i < n; i++)
   {
      queue.offer(new Person(i, arr[i]));
   }
   
   while (!queue.isEmpty())
   {
      Person tmp = queue.poll();
      for (Person x : queue)
      {
         if (x.priority > tmp.priority)
         {
            queue.offer(tmp);
            tmp = null;
            break;
         }
      }
      
      if (tmp != null) { // tmp의 우선순위가 제일 높다는 뜻 !
         answer++;
         if (tmp.id == m)
            return answer;
      }
   }
   
   return answer;
}

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

👾 : 강사님은 좀 더 간단하게 풀었다. Person 이라는 객체를 만들어서 id는 순서, priority는 위험도의 값을 넣어주도록 했다. 

그 다음 Person을 담는 Queue를 생성해주고, queue에 offer로 Person 객체를 생성해서 id와 priority의 값을 넣어줬다. 

 

그리고 while 반복문에서 queue가 비어있지 않을 때까지 반복하는데 

먼저 queue에서 poll한 값을 꺼내서 tmp 라는 Person 객체를 만들고, for 반복문을 통해서 queue 값을 하나씩 꺼내서 tmp의 priority의 값과 queue에서 꺼낸 x의 priority 값 중에서 tmp의 priority가 더 작으면 queue에서 poll 한 값을 다시 queue에 offer 해준다. 그리고 tmp 값을 null로 바꿔주고 break 해주면 된다. (더 이상 반복문을 돌 필요는 없으니!) 

 

그리고 tmp가 null이 아니라는 뜻은 tmp가 지금 제일 우선순위가 높은 환자라는 뜻이기 때문에 우선 answer의 값을 +1 해주고, 그 다음 tmp의 id 가 주어진 값 m 과 동일하다면 M 번째 환자라는 뜻이기 때문에 answer를 리턴해주면 된다.