[인프런 알고리즘] Chpater 5, 8번 문제(응급실)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

첫 번째 코드(시간 복잡도 O(N^2))

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class sec05_08 {
    public static class Person
    {
        private int priority;
        private int idx;

        Person(int priority, int idx)
        {
            this.priority = priority;
            this.idx = idx;
        }
    }

    public static int solution(int N, int M, int[] arr) 
    {
        Queue<Person> queue = new LinkedList<>();
        for (int i = 0; i < N; ++i) queue.offer(new Person(arr[i], i));

        int count = 0;
        while (!queue.isEmpty())
        {
            Person current = queue.poll();
            boolean hasHigherPriority = false;

            for (Person person : queue) {
                if (person.priority > current.priority)
                {
                    hasHigherPriority = true;
                    break;
                }
            }

            if (hasHigherPriority) queue.offer(current);
            else 
            {
                count++;
                if (current.idx == M) return count;
            }
        }

        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(N, M, arr));
    }
}

 

두 번째 코드(시간 복잡도 개선 O(N log N))

package inflearn_algorithm.chapter5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class sec05_08 {
    public static class Person
    {
        private int priority;
        private int idx;

        Person(int priority, int idx)
        {
            this.priority = priority;
            this.idx = idx;
        }
    }


    public static int solution(int N, int M, int[] arr)
    {
        Queue<Person> que = new LinkedList<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < N; ++i)
        {
            que.offer(new Person(arr[i], i));
            pq.offer(arr[i]);
        }

        int count = 0;
        while (!que.isEmpty())
        {
            Person current = que.poll();
            if (current.priority == pq.peek())
            {
                count++;
                pq.poll();
                if (current.idx == M) return count;
            }
            else que.offer(current);
        }

        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(N, M, arr));
    }
}

 

설명

첫 번째 코드 설명

• 큐에서 환자를 하나씩 꺼내어(poll) 현재 큐에 남아 있는 다른 환자들과 우선순위를 비교한다.
• 만약 현재 환자보다 우선순위가 높은 다른 환자가 있으면, 현재 환자를 다시 큐의 뒤로 넣는다.
• 그렇지 않으면 현재 환자를 진료하고(count 증가), 이 환자가 목표로 한 환자(M)인지 확인한다. 만약 맞다면, 현재까지의 count 값을 반환하여 몇 번째로 진료를 받았는지 결과를 돌려준다.

 

두 번째 코드 설명

• Queue<Person> que에 모든 환자를 입력 순서대로 추가한다.
• PriorityQueue<Integer> pq는 환자의 우선순위를 내림차순으로 저장하여, 항상 가장 높은 우선순위를 빠르게 조회할 수 있게 한다.
• 큐에서 환자를 하나씩 꺼내어(poll), 그 환자의 우선순위가 현재 대기 중인 환자들 중 가장 높은지 확인한다(pq.peek()).
• 만약 가장 높은 우선순위라면 그 환자는 진료를 받게 되고(count 증가), 우선순위 큐에서도 해당 우선순위를 제거한다(pq.poll()).
• 목표 환자(M)가 진료를 받게 되면 그때까지의 count를 반환하여 몇 번째로 진료를 받았는지를 반환한다.
• 만약 현재 환자가 가장 높은 우선순위가 아니라면 큐의 끝으로 다시 보내서 나중에 다시 확인하도록 한다.