[프로그래머스] #lv.3 - 숫자 게임 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/12987

프로그래머스

 

# 힌트

우선순위 큐. 참고로 DFS로 접근하면 입력 크기가 10만이기 때문에 안 된다.

 

해답 보기

문제 풀이의 핵심 아이디어는 B는 A보다 크고 B가 가지고 있는 수 중 제일 작은 수로 이겨야 한다는 점이다.

즉, A = 3 이고 B = 4,5이면 B는 4로 이겨야 한다.

 

각 배열를 역순으로 정렬한다.

A = [7,5,3,1]

B = [8,6,2,2]

7, 8 비교 7 < 8 이므로 win + 1

5 < 6 이므로 win + 1

3 < 2 는 아니므로 넘어간다. 

1 < 2 이므로 win + 1

 

이를 우선순위 큐를 사용해서 구현하면 다음과 같은 로직을 따른다.

1. 역순 정렬인 우선순위 큐에 A, B 각각의 원소를 넣는다.

2. A의 길이 (B의 길이와 동일) 만큼 다음을 반복

2-1. A 큐와 B 큐에서 각각 원소를 꺼내서 비교한다.

2-2. A < B 이면 win + 1

2-3  A >= B 이면 꺼낸 B를 다시 B 큐에 집어넣는다.

3. win return

 

2-3 번은 B가 가지고 있는 수 중 A보단 크지만 가장 작은 수를 다시 우선순위 큐에서 꺼낼 수 있도록 하기 위해 다시 넣어주는 것이다.

 

    static PriorityQueue<Integer> getQueue(int[] arr) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        for (int n : arr) pq.add(n);
        return pq;
    }

    public static int solution(int[] A, int[] B) {
        PriorityQueue<Integer> aq = getQueue(A);
        PriorityQueue<Integer> bq = getQueue(B);
        int win = 0;
        for (int i = 0; i < A.length; i++) {
            int a = aq.poll();
            int b = bq.poll();
            if (a < b) win++;
            else bq.add(b);
        }
        return win;
    }