프로그래머스 - 숫자 게임(Java)

힙(Heap) 구조를 이용한 구현 문제입니다.

 

이 문제를 풀기 위해서는 한 가지의 아이디어가 필요합니다.

'A의 큰 숫자를 B의 큰 숫자로 대응시켜야 한다.'

 

A에는 {5, 1, 3, 7}가 있고, B에는 {1, 1, 6, 8}이 있다고 가정하겠습니다.

A의 {5}는 B의 {6}과 {8}로 해결할 수 있습니다.

B의 {8}로 A의 {5}를 이기게 되면, B의 {6}은 {3}을 이겨 최대가 2가 됩니다.

하지만, B이 {8} A의 {7}을 이기면 최대가 3이 됩니다.

 

배열을 정렬하게 된다면 일반적으로 O(nlogn)의 시간이 걸리게 됩니다.

하지만, 단순히 힙 구조에 넣게 되면 배열 정렬하면서 O(N)의 시간으로 정렬된 값들을 얻을 수 있습니다.

단, 이 문제의 특성상 거의 모든 원소의 값을 크기 순으로 확인 및 비교해야 하므로 힙 구조를 이용한 것이지,

특정 위치의 값을 이용하는 문제들은 힙 구조가 아닌 배열을 정렬하는게 더 이로울 것입니다.

 

저의 경우 do-while을 사용해 값들을 비교해 봤습니다.

 

[구현 코드]

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    private static int n;

    public static int solution(int[] A, int[] B) {
        n = B.length;

        PriorityQueue<Integer> aPq = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> bPq = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < n; i++) {
            aPq.add(A[i]);
            bPq.add(B[i]);
        }


        int cnt = 0;

        int b = bPq.poll();
        do {
            int a = aPq.poll();
            if (b > a) {
                if(!bPq.isEmpty()) b = bPq.poll();
                cnt++;
            }
        } while (!aPq.isEmpty());

        return cnt;
    }
}