[프로그래머스] Lv2. 최솟값 만들기 - 우선순위 큐

최솟값 만들기

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

문제

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.

배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
• A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수
• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

풀이

배열을 ArrayList로 받아서

Collections로 A는 오름차 B는 내림차로 정렬하여

같은 index에 위치한 수를 곱했다

아무리 생각해도 너무 깔끔한 생각이라고 생각했음.

import java.util.*;

class Solution
{
    public int solution(int []A, int []B)
    {
        ArrayList<Integer> arrA = new ArrayList<Integer>();
        ArrayList<Integer> arrB = new ArrayList<Integer>();
        //ArrayList에 더해주기
        for(int i = 0; i < A.length; i++){
            arrA.add(A[i]);
            arrB.add(B[i]);
        }
        
        Collections.sort(arrA);
        Collections.sort(arrB);
        Collections.reverse(arrB);
        int answer = 0;
        
        for(int i = 0; i < A.length; i++){
            answer += arrA.get(i) * arrB.get(i);
        }

        return answer;
    }
}

테케는 모두 통과했으나 , 시간초과가 나버림 ^^

Collections.sort 시간복잡도 → 평균, 최악 : O(nlog(n))

찾아보니 우선순위 큐를 쓰란다.. 아니 이런문제에 그런 함정이!

Priority Queue 시간복잡도 → O(N)

StackOverFlow에도 관련 질문이 많다

https://stackoverflow.com/questions/56506410/why-is-on-better-than-o-nlogn

여튼 sort로 복잡도 문제가 생기면 우선순위큐를 써보는 방향으로,,

import java.util.*;

class Solution
{
    public int solution(int []A, int []B)
    {
        PriorityQueue<Integer> queue1 = new PriorityQueue<Integer>();
        PriorityQueue<Integer> queue2 = new PriorityQueue<Integer>(Collections.reverseOrder());
        
        for(int i = 0; i < A.length; i++){
            queue1.add(A[i]);
            queue2.add(B[i]);
        }
        int answer = 0;
        while(!queue1.isEmpty()){
            answer += queue1.poll() * queue2.poll();
        }
        return answer;
    }
}

Priority Queue 란?!

Queue와 구조가 비슷하다

Queue는 먼저들어온 순서대로 데이터가 나가지만,

Priority Queue는 데이터의 우선순위를 정하여 우선순위 큐는 우선순위가 높은 순서대로 나가게 된다! 또한 값의 비교를 해야하기에 null은 허용하지 않고, 내부는 이진트리 힙으로 구성되어 있다.

Priority Queue 선언 java.util.PriorityQueue

// Integer 타입으로 우선순위 큐 선언 (작은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

// Integer 타입으로 우선순위 큐 선언 (큰 숫자 순으로 우선순위 결정) 
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());		
		
// Integer 타입으로 우선순위 큐 선언 (작은 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQueue = new PriorityQueue<>();

// Integer 타입으로 우선순위 큐 선언 (큰 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

사용법은 Queue와 거의 동일함

✅ 값 추가에는 add(), offer() 사용

• add() : 큐가 꽉 찬 경우 IllegalStateException 에러 발생
• offer() : 큐가 꽉 찬 경우 false 반환

✅ 값 삭제에는 poll(), remove(), clear() 사용. remove(int index) 사용시 index순위의 값을 삭제

• remove() : 큐가 비어있는 경우 NoSuchElementException 에러 발생
• poll() : 큐가 비어 있을 경우 null 반환
• clear() : 큐 비우기

✅ 맨 앞 값 확인 peek(), element() 사용

• peek() : 비어 있는 경우 null 반환
• element() : 큐가 비어 있는 경우 NoSuchElementException 에러