public static 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[A.length - 1 - i];
}
return answer;
}리팩토링
int n = A.length;
for (int i = 0; i < n; i++) {
answer += A[i] * B[n - 1 - i];
}
- 이런 식으로 변수로 길이를 추출해두면 더 깔끔하고 의도가 분명해진다.
풀이
-
A를 오름차순, B를 내림차순처럼 처리하면서 곱셈 진행
-
즉, A의 가장 작은 수 × B의 가장 큰 수, 다음 작은 수 × 다음 큰 수…
-
곱의 총합을 최소화하는 방법으로 접근
내 생각 흐름이 괜찮은 건지, 좀 더 나은 접근 법이나 개념을 알아가기 위해 지피티와 함께 검토를 해보았다.
수학적으로 검증된 최적해법이라고 한다! :)
-
수학적으로도 그리디하게 A는 오름차순, B는 내림차순 정렬해서 곱하면 최소합이 된다.
-
정렬 + 순차 곱셈으로
O(N log N)에 해결 → 매우 효율적!
🌟 알고 있으면 좋은 개념
| 개념 | 설명 |
|---|---|
| 그리디 알고리즘 (Greedy) | 현재 상황에서 가장 좋은 선택을 반복해서 최적해에 도달하는 전략. 이 문제는 그리디가 정확히 적용됨 |
| 정렬 (Sorting) | 문제의 조건이나 최적화를 위해 입력을 오름/내림차순 정렬해서 활용하는 경우 많음 |
| 투 포인터 / 역 인덱스 | 정렬된 배열을 양쪽에서 접근해서 조합을 만드는 전략. 여기선 B.length - 1 - i 같은 식이 그 예 |
Collections.reverseOrder() 이용한 내림차순
만약 B를 명시적으로 내림차순 정렬하고 싶다면:
Integer[] B = {5, 4, 4}; // int[] → Integer[]로 바꿔야 함
Arrays.sort(B, Collections.reverseOrder());
이런 방법도 있다.
하지만 현재 방식처럼 A[i] * B[n - 1 - i]로 역순 인덱스 사용하는 게 더 간단하고 빠르다!
정렬과 그리디 조합 문제는 자주 등장하는 패턴이기 때문에, 이번 문제를 통해 개념 + 구현 능력을 함께 키울 수 있었다.
