[파이썬 PYTHON · 자바 JAVA] 프로그래머스 【최솟값 만들기】

---

자바 코드

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[A.length-i-1];
        }
        
        return answer;
    }
}

파이썬 코드

from itertools import combinations    

def solution(A,B):
    A.sort()
    B.sort(reverse = True)
    
    ans = 0
    
    for i in range(len(A)):
        ans+=A[i]*B[i]
    
    return ans

처음에 봤을 때, 조합으로 하는건가 싶었는데 더 생각해보니 규칙을 찾을 수 있었다.

 

먼저 A와 B는 길이가 같다.

 

A는 오름차순 정렬하고 B는 내림차순한뒤, 같은 인덱스에 있는 요소들을 곱한게 최솟값이 나온다.

 

흠 증명이 맞는지는 모르겠지만

 

A = [a , a+1] 

B = [b+1 , b] 이라고 할때

 

정렬 뒤, 같은 인덱스끼리 곱했을 때

a*(b+1) + (a+1)*b = 2ab+a+b 가 나오고

 

다른 인덱스끼리 곱하면

a*(b)+(a+1)*(b+1) = 2ab+a+b+1 이 나온다.

 

파이썬은 내림차순 정렬이 쉬워서 내림차순으로 했고 자바는 오름차순한다음에 인덱스만 바꿔서 값을 구하였다.