문제 설명
길이가 같은 배열 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 이하의 자연수
입출력 예
| A | B | answer |
|---|---|---|
| [1, 4, 2] | [5, 4, 4] | 29 |
| [1,2] | [3,4] | 10 |
입출력 예 설명
입출력 예 #1문제의 예시와 같습니다.
입출력 예 #2A에서 첫번째 숫자인 1, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 4) 다음, A에서 두번째 숫자인 2, B에서 첫번째 숫자인 3을 뽑아 곱하여 더합니다. (누적된 값 : 4 + 6 = 10)이 경우가 최소이므로 10을 return 합니다.
나의 풀이
문제를 해결하는 알고리즘을 생각해 내는 것 자체는 어렵지 않았다.
하나의 배열은 오름차순, 하나의 배열은 내림차순으로 정렬을 해준 뒤, 반복문을 통해 첫 번째 인덱스부터 끝까지 접근하면 답을 구할 수 있기 때문이다.
이러한 접근법으로 풀어낸 코드는 다음과 같다
import java.util.Arrays;
import java.util.Collections;
class Solution
{
public int solution(int []A, int []B)
{
int answer = 0;
Arrays.sort(A);
Integer[] b = Arrays.stream(B).boxed().toArray(Integer[]::new);
Arrays.sort(b, Collections.reverseOrder());
for (int i = 0; i < b.length; i++) {
answer += A[i] * b[i];
}
return answer;
}
}하지만 이번 문제는 평범한 알고리즘 문제가 아닌 시간 효율성 역시 생각해야 하는 문제였다.
모든 테스트 케이스를 통과했지만 효율성 테스트에서 단 하나의 케이스를 통과하지 못하였다. 답을 구하는 알고리즘 자체는 각 인덱스의 값을 곱해주는 것 말고는 특별할 게 없기 때문에 자료를 담는 자료구조형에서 해답을 찾아야 한다고 생각했다.
인덱스를 갖는
Array보다 인덱스를 갖지 않는Queue, Stack등의 자료형이 이번 문제풀이에 유리할 것이라고 생각했기 때문이다.
결국 적합한 자료구조형을 찾고 정렬을 진행한 뒤 값을 도출해내는 과정인데, PriorytQueue가 가장 적합한 자료구조임을 파악했다.
PriorityQueue란?
일반적으로 Queue 자료구조는 선입선출의 구조로 먼저 들어온 데이터가 먼저 나가는 구조를 가지게 된다. PriorityQueue는 들어온 순서대로 데이터가 나가는 것이 아닌, 내부적으로 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조이다.
PriorityQueue의 특징
- 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다
- 내부 요소는 Heap으로 구성된 이진트리 구조로 이루어져 있다
- 내부구조가 Heap으로 구성되어 있기에 시간 복잡도는 O(NlogN)
여기서 Heap이란 메모리 영역의 Heap이 아닌 완전 이진 트리의 한 종류로 최댓값이나 최솟값을 빠르게 찾아내기 위해 고안된 자료구조이다!
즉, PriorytQueue 는 결정된 우선순위를 바탕으로 정렬이 완료된 상태이기 때문에 이번 문제를 풀기에 아주 적합한 자료구조라고 볼 수 있다.
따라서 이를 적용한 코드는 다음과 같다
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
class Solution
{
public int solution(int []A, int []B)
{
int answer = 0;
PriorityQueue<Integer> queue1 = new PriorityQueue<>();
PriorityQueue<Integer> queue2 = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < A.length; i++) {
queue1.add(A[i]);
queue2.add(B[i]);
}
while (!queue1.isEmpty()) {
answer += queue1.poll() * queue2.poll();
}
return answer;
}
}
