프로그래머스 lv2 - 최솟값 만들기

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

프로그래머스

 

입출력 예를 보니까 A에서는 최솟값을, B에서는 최댓값을 찾아 둘을 곱하면 answer를 찾을 수 있는 것처럼 보인다.

def solution(A,B):
    answer = 0
    
     A_copy = A
     B_copy = B
    
     while len(A_copy)>0:
         answer+= (min(A_copy)*max(B_copy))
         A_copy.remove(min(A_copy))
         B_copy.remove(max(B_copy))
         
  	return answer

이렇게 풀었는데 효율성에서 탈락했다. 왜 효율성에서 탈락했냐면 저걸 하기 위해서는 계속 매번 answer에 값을 더할 때마다 min과 max를 해야 해서 O(2n)이 추가되고, remove도 해야 하니까 또 O(2n)이 추가되어서 결국 O(4n)의 시간이 걸리기 때문이다.

 

따라서 사전에 미리 A는 오름차순 정렬을, B는 내림차순 정렬을 해 주면 굳이 max, min을 할 이유도 remove할 이유도 없어진다.

def solution(A,B):
    answer = 0

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