[알고리즘] 5-8 응급실 - Queue (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의)

인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 예습 풀이 코드, 강의 수강 후 복습 풀이 코드를 정리하고 있습니다.

• 문제 링크 : https://cote.inflearn.com/contest/10/problem/05-08

예습 풀이

• Queue 자료구조 사용
• pos 변수로 m번째 환자 위치 추적

package inflearn.stack_queue;

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

//응급실
public class Main5_8 {

    public static int solution(int n, int m, int[] patients) {
        int pos = m;
        int answer = 0;
        Queue<Integer> queue = new LinkedList<>();

        for (int i : patients) {
            queue.offer(i);
        }

        while (!queue.isEmpty()) {

            int poll = queue.poll();

            if (poll >= Collections.max(queue)) { //위험도가 가장 높다면
                answer++;

                if (pos == 0) {
                    return answer;
                }

            } else {

                queue.offer(poll);

                if (pos == 0) {
                    pos = queue.size();
                }
            }

            pos--;
        }

        return answer;
    }


    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());
        int[] patients = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; st.hasMoreTokens(); i++) {
            patients[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(solution2(n, m, patients));

        br.close();
    }

}

강의 풀이

• Queue 자료구조 사용
• m번 환자의 위치를 추적하기 위해 Person 클래스를 만들어 사용

class  Person {
    int id;
    int priority;

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

public static int solution2(int n, int m, int[] patients) {
    int answer = 0;
    Queue<Person> queue = new LinkedList<>();

    for (int i = 0; i < n; i++) {
        queue.offer(new Person(i, patients[i]));
    }

    while (!queue.isEmpty()) {
        Person temp = queue.poll();

        for (Person p : queue) {
            if (temp.priority < p.priority) {
                queue.offer(temp);
                temp = null;
                break;
            }
        }

        if (temp != null) { //위험도가 가장 높다면
            answer++;
            if (temp.id == m) {
                return answer;
            }
        }
    }

    return answer;
}