프로그래머스 최솟값 만들기 java

문제링크

문제 접근

• 두 배열 원소 곱한 값을 다 더한 결과의 최솟값
• A,B 정렬해서 A는 큰놈부터 B는 작은놈부터 서로 곱하면 최솟값

코드

import java.util.*;
class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        
        for(int i=0;i<A.length;i++){
            answer += A[i] * B[B.length - 1 - i];
        }
        return answer;
    }
}

결과

• 처음 채점했을때에 효율성 테스트 통과 못했는데 갑자기 됨
• 이유는 배열 정렬 Arrays.sort 때문이라고 생각
• 배열 대신 우선순위 큐 활용해보자

우선순위 큐 코드

import java.util.*;
class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        PriorityQueue<Integer> AQ = new PriorityQueue<>();
        PriorityQueue<Integer> BQ = new PriorityQueue<>(Collections.reverseOrder());

        for(int i=0;i<A.length;i++){
            BQ.add(B[i]);
            AQ.add(A[i]);
        }
        while(!AQ.isEmpty()){
            answer += AQ.poll() * BQ.poll();
        }
        return answer;
    }
}

결과

정리

• 오히려 우선순위를 활용한 결과가 시간 더 오래 걸림
• 배열 sort 채점이 처음엔 통과 못했는데 서버 문제인가??
• 문제 포인트는 한 배열은 작은 값부터 다른 배열은 큰 값부터 서로 곱한 값하여 더한 값이 최솟값이라는 점