최솟값 만들기

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

프로그래머스

 

두 배열의 모든 원소를 곱하는 방식으로 풀게 되면 시간 복잡도가 N^2이 되어버림.

 

제한 조건이 자연수이므로 여러 케이스를 생각 했을 때, 두 배열의 최대값끼리 곱하는 순간, 최솟값과 멀어짐.

 

그러므로 하나의 배열은 오름차순, 하나의 배열은 내림차순 정렬 -> 작은값 * 큰값 을 곱해서 합산하여 결과를 구함

 

딱히 반례를 찾지도 못하겠고, 테스트 케이스도 무리없이 통과함.

 

import java.util.*;

class Solution
{
    public int solution(int []A, int []B)
    {

        int answer = 0;
        
        // A와 B를 정렬. B를 역순 정렬하면 최종 계산시 편리하지만, 정렬과정이 귀찮아짐.
        Arrays.sort(A);
        Arrays.sort(B);
        
        int len = A.length;
        for (int i = 0; i < len; i++) {
            // 오름차순 정렬된 A와 내림차순 정렬된(오름차순 정렬되어있지만 역순으로 가져오니까 내림차순이라 침) B의 각 원소를 곱함
            answer += (A[i] * B[len - i - 1]);
        }

        return answer;
    }
}