프로그래머스(입국 심사, 이중우선순위 큐) - Java

[입국 심사]

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

 

* 조건

1. n명이 입국 심사를 위해 대기중이다
2. 심사관마다 심사하는 소요 시간인 times[]가 주어진다
3. 모든 사람이 심사를 받는데 걸리는 최소 시간을 구한다
4. 비어있거나 더 빨리 끝나는 심사대가 있다면 기다렸다가 심사를 받아도 된다

 

* 알고리즘

• 이분 탐색

* 로직(Logic)

• times[]를 오름차순 정렬한다
• 초기에는 비어있는 심사대 수만큼은 바로 심사하게 해주고, 남은 사람의 수 * times[]의 가장 큰 값이 곧 최대로 나올수 있는 최대 소요 시간이다
• 이분 탐색을 통해 기준이 되는 심사 시간을 통해 심사 가능한 경우를 카운팅한다 (count)
• count < n 이라면 front = mid + 1, count >= n이라면 rear = mid - 1을 통해 최소 시간이 나올 때까지 반복한다

 

import java.util.Arrays;

public class Problem_ImmigrationExamination {

    public static void main(String[] args) {
        int n = 6;
        int[] times = {7, 10};

        long answer = solution(n , times);
        System.out.println(answer);
    }

    public static long solution(int n, int[] times) {
        long answer = 0;
        //오름차순 정렬
        Arrays.sort(times);

        //이분탐색을 위한 초기 범위 설정
        //처음에는 비어있는 심사관 수만큼은 바로 심사했다고 생각하고 최대 걸리는 시간
        int baseNum = (n - times.length) > 1 ? (n - times.length) : 1;
        long front = 1;
        long rear = (long) times[times.length-1] * baseNum;
        answer = rear;

        while (front <= rear){
            //기준 시간
            long mid = (front + rear) / 2;

            //기준 시간보다 작다면 해당 심사 시간으로 가능한 심사개수 카운팅
            long count = countTime(mid, times);

            if(count < n) front = mid+1;
            else {
                answer = Math.min(answer, mid);
                rear = mid-1;
            }
        }

        return answer;
    }

    private static long countTime(long mid, int[] times) {
        long count = 0;
        for(int i=0; i<times.length; ++i){
            count += (mid / times[i]);
        }
        return count;
    }
}

 

---

[이중 우선순위 큐]

 

* 조건

1. 명령어가 주어진다
2. "I 숫자": 숫자를 insert, "D 1": 큐에서 최댓값을 삭제, "D -1": 큐에서 최솟값을 삭제
3. D 명령 수행 시, 큐가 비어있으면 명령을 무시한다
4. 명령에 맞게 수행을 한 후 최댓값과 최솟값을 출력한다

* 알고리즘

• 우선순위 큐(힙 구조) or 원형 큐

* 로직(Logic)

• 최솟값을 삭제하기 위한 오름차순 정렬이 되는 우선순위 큐를 만든다 (A)
• 최댓값을 삭제하기 위한 내림차순 정렬이 되는 우선순위 큐를 만든다 (B)
• 삽입의 경우 그대로 두 개의 큐에 넣어준다
• 삭제의 경우
  • 만약 D 1이라면, B큐에서 최댓값을 가져오고 해당 값을 각각의 큐에서 지워준다
  • 만약 D -1이라면, A큐에서 최솟값을 가져오고 해당 값을 각각의 큐에서 지워준다
• 만약 큐에 아무 값도 없다면 최대 최소는 0이다
• 존재한다면 A의 최솟값, B의 최댓값을 넣어준다

 

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class NumberQueue implements Comparable<NumberQueue> {
    public int num;

    public NumberQueue(int num) {
        this.num = num;
    }

    @Override
    public int compareTo(NumberQueue o) {
        if(this.num > o.num) return 1;
        return -1;
    }
}

public class Problem_2PriorityQueue {

    public static void main(String[] args) {
        String[] operations = {
                "I 16","D 1"
//                "I 7","I 5","I -5","D -1"
        };

        int[] answer = solution(operations);
        for(int ans : answer)
            System.out.println(ans);
    }

    public static int[] solution(String[] operations) {
        int[] answer = new int[2];

        PriorityQueue<NumberQueue> priorityQueue = new PriorityQueue<>();
        PriorityQueue<NumberQueue> reverseQueue = new PriorityQueue<>(new Comparator<NumberQueue>() {
            @Override
            public int compare(NumberQueue o1, NumberQueue o2) {
                return o2.num - o1.num;
            }
        });

        StringTokenizer st;
        for(String input : operations){
            st = new StringTokenizer(input, " ");
            String oper = st.nextToken();
            int num = Integer.parseInt(st.nextToken());

            //insert
            if(oper.equals("I")){
                NumberQueue numberQueue = new NumberQueue(num);
                priorityQueue.offer(numberQueue);
                reverseQueue.offer(numberQueue);
            }

            //delete
            else if(oper.equals("D") && priorityQueue.size() > 0){
                //만약 숫자가 -1(음수) -> 큐에서 최솟값 삭제
                if(num == -1) {
                    NumberQueue min = priorityQueue.peek();
                    priorityQueue.remove(min);
                    reverseQueue.remove(min);
                }

                //만약 숫자가 1(양수) -> 큐에서 최댓값 삭제
                else if(num == 1) {
                    NumberQueue max = reverseQueue.peek();
                    priorityQueue.remove(max);
                    reverseQueue.remove(max);
                }
            }
        }

        if(priorityQueue.isEmpty()) answer[0] = answer[1] = 0;
        else {
            answer[0] = reverseQueue.peek().num;
            answer[1] = priorityQueue.peek().num;
        }

        return answer;
    }
}

 

원형 큐를 사용해 한쪽으로만 정렬을 하여 맨 앞과 끝을 관리해도 괜찮을거 같다는 것을 느꼈다.