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

문제 설명

프로그래머스 레벨 2의 문제입니다.

 

같은 길이의 배열 두개에서 두 개의 숫자를 뽑아 곱한 값을 계속 더합니다. 그렇게 더한 값이 가장 작도록 될때 가장 작은 합을 구하는 문제입니다.

 

입출력 예 2번의 경우 (1 * 4) + (2 * 3) = 10와 같이 풀 수 있습니다.

풀이

def solution(A, B):
    min_sum = 0
    arr_len = len(A)

    for i in range(arr_len):
        min_value = min(A)
        max_value = max(B)

        A.remove(min_value)
        B.remove(max_value)

        min_sum += (min_value * max_value)

    return min_sum

위 풀이는 효율성을 틀린 풀이입니다. 가장 먼저 떠오른 생각대로 작성한 코드입니다. 정확한 풀이가 아니기에 간단히 설명하겠습니다.

배열의 길이만큼 순회하며 (배열 A의 가장 작은 값) * (배열 B의 가장 큰 값)을 계속 더해가면 가장 작은 합이 나온다고 생각했습니다.

 

정답은 모두 맞았지만 효율성에서 배열을 순회할 때마다 min, max, remove가 실행된다는 점에서 틀렸습니다.

 

def solution(a: list, b: list):
    a.sort()
    b.sort(reverse=True)

    min_sum = 0
    for i in range(len(a)):
        min_sum += (a[i] * b[i])

    return min_sum

변수 설명

min_sum: 가장 최소가 되는 합입니다.

 

간단 설명

각 배열을 sort합니다. 둘 중 하나의 배열은 오름차순, 하나는 내림차순으로 정렬합니다.

 

이로 인해 배열의 순서대로 곱해 넣으면 배열의 (배열의 작은 값) * (배열의 큰 값) 순서로 곱해지게 됩니다.