프로그래머스 level2 _ 최솟값 만들기 [Python]

 처음에는 가능한 모든 조합을 다 계산해서 최솟값을 찾으려고 하였다.

그러나 A,B로 부터 [(1,5),(2,6),(3,7)], [(1,6),(2,5),(3,7)], [(1,7),(2,5),(3,6)], ... 의 가능한 조합 전체를 뽑아내는 코드를 구현하지 못했다.

또 구현한다고 하더라도 A,B의 크기가 1,000이하의 자연수 이기 때문에 너무 오래걸릴 것이다.

 

정답 코드는 아래와 같다.

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

A,B 중 하나는 역순으로, 나머지 하나는 순서대로 정렬한 후 인덱스 순서대로 곱한 후 더하면 그것이 합의 최솟값이 된다.

이러한 방법이 모든 경우에서 항상 최소임을 보장하는가에 대해 고민을 조금 해봤는데, 큰 값은 무조건 작은 값과 곱해서 그 크기를 낮춰줘야하기 때문에 조금만 생각해보면 보장한다는 것을 알 수 있다.

 

조금 더 간단하게 한줄로서 위 코드를 나타낼 수 있는데,

def solution(A,B):
    return sum(a*b for a, b in zip(sorted(A), sorted(B, reverse = True)))

역시 zip 함수 등을 잘 사용하는 것이 중요한 것 같다.