[프로그래머스] 자바 LV3. 숫자 게임

😖 틀린 풀이

import java.util.*;

class Solution {
    private int getDifference(int num, int[] B){
        int compareDifference = Integer.MAX_VALUE;
        int index = -1;
        
        for(int i=0; i<B.length; i++){
            if(B[i] == 0){
                continue;
            }
            
            int difference = B[i] - num;
            if(difference>0 && compareDifference>difference){
                compareDifference = difference;
                index = i;
            }
        }
        return index;
    } 
    
    public int solution(int[] A, int[] B) {
        int answer = 0;
        
        for(int i=0; i<A.length; i++){
            int index = getDifference(A[i], B);
            
            if(index == -1){
                continue;
            }
            
            B[index] = 0;
            answer++;
        }
        
        return answer;
    }
}

 

위의 코드로는 모든 테케는 통과하지만 효율성에서 모두 틀렸다고 떴다.

이는 O(n^2) 의 시간복잡도로 풀었다. B 가 갖고 있는 숫자 중에서 A 가 낸 숫자와 가장 작은 차이를 보이는 숫자를 골라 조합을 만들고자 했다. 접근 방식은 맞은 듯 하나 효율성에서 자꾸 오류가 떠서 오랫동안 고민을 했다..

 

계속 생각한 지점들은

1. 정렬을 해야 한다. (그러나 효과적으로 빠르게)

2. 단순히 정렬만 해서는 안된다. 

예를 들어, [8,5,3,1] [2,6,7,2] 가 있다고 가정해보자. 단순히 정렬만을 한다면 얻을 수 있는 점수는 2점이지만 최대로 얻을 수 있는 점수는 3점이다.

 

🦊 맞는 풀이

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int l = A.length;
        int answer = 0;
        PriorityQueue<Integer> pqA = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> pqB = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i=0; i<l; i++){
            pqA.add(A[i]);
            pqB.add(B[i]);
        }
        
        while(!pqA.isEmpty()){
            int numA = pqA.poll();
            int numB = pqB.peek();
            
            if(numA >= numB){
                continue;
            }
            
            pqB.poll();
            
            if(numA < numB){
                answer++;
            }
        }
        return answer;
    }
}

1. 정렬을 효과적으로 하기 위해서 우선순위 큐를 사용했다.

2. 단순히 정렬만 해서는 안되기 때문에, peek 을 사용했다.

 

만약, [8,5,3,1] [2,6,7,2] 라고 한다면 pqA 는 [8,5,3,2]/ pqB 는 [7,6,2,2] 가 될 것이다. 

8은 B의 어떤 큰 수가 와도 이길 수 없기 때문에 7을 여기에 배치하는 것은 비효율적인 선택이기에 그냥 넘어가는 것이 옳다.

따라서 [5,3,1] [7,6,2,2] 가 되고, 5가 7과 배치되고, 3이 6과 배치되고, 1이 2와 배치되고 이전에 그냥 넘어갔던 8이 2와 배치되어야 한다.

 

따라서 numA 가 numB 보다 크거나 같을 경우에는 그냥 넘어가고, numA 가 더 작다면 pqB 에서 숫자를 하나 꺼내고 점수를 증가시키는 것이 옳다.