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

import heapq
def solution(A,B):
    
    result = 0
    count = len(A)
    
    # A에 대한 최소 힙 / 최대 힙, B에 대한 최소 힙 / 최대 힙 
    min_heap_a, max_heap_a, min_heap_b, max_heap_b = [], [], [], []
    
    for a in A:
        heapq.heappush(min_heap_a,a)
        heapq.heappush(max_heap_a,-a)
    for b in B:
        heapq.heappush(min_heap_b,b)
        heapq.heappush(max_heap_b,-b)
    
    while count > 0: # 원소의 개수만큼 반복
        min_A, max_A, min_B, max_B = min_heap_a[0], -max_heap_a[0], min_heap_b[0], -max_heap_b[0]
        
        if min_A * max_B < min_B * max_A: # A의 최솟값 * B의 최댓값이 더 작은 경우
            heapq.heappop(min_heap_a)
            heapq.heappop(max_heap_b)
            result += (min_A * max_B)
        else: # B의 최솟값 * A의 최댓값이 더 작은 경우
            heapq.heappop(min_heap_b)
            heapq.heappop(max_heap_a)
            result += (min_B * max_A)
            
        count -= 1
        
    # while A and B: (시간초과 코드)
    #     min_A, max_A, min_B, max_B = min(A), max(A), min(B), max(B)
    #     if min_A * max_B < min_B * max_A:
    #         A.remove(min_A)
    #         B.remove(max_B)
    #         result += (min_A * max_B)
    #     else:
    #         A.remove(max_A)
    #         B.remove(min_B)
    #         result += (max_A * min_B)
        
    return result

 

이 문제는 길이가 같은 두 배열 A와 B에서 각각 하나의 숫자를 뽑아서 곱한 값을 누적시킬 때, 최조적으로 누적된 값의 최솟값을 구하는 문제이다.

 

처음에 해당 문제를 접근할 때, A와 B 각각의 최솟값과 최댓값을 구하여 (A의 최솟값 * B의 최댓값)과 (B의 최솟값 * A의 최댓값)을 비교하여 더 작은 값을 누적시켜주는 방식으로 풀이하였다.(최소나 최대를 구하는 연산을 최소화하기 위해 heapq 사용)

 

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

 

하지만 다른 사람의 풀이를 참고해본 결과, 결국에는 A와 B를 서로 반대로 정렬하고 그 곱을 누적시켜주면 되는 문제(각각의 최소와 최대를 곱해주면서 누적시켜주면 되기 때문)였다.

 

zip 함수의 사용법과, 최대 최소에 관한 문제는 정렬로 더 효율적으로 풀 수 있다는 사실을 배울 수 있었던 문제였다 :)