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

📝 문제설명

출처참고

🔗 출처

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

✅ 아이디어

1. 어떻게 하면 최솟값을 표현할 수 있을까?

✅ 정답

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

처음에는 어떻게 하면 최솟값을 만들 수 있을까? 브루스탐색으로 생각해보았으나, 조금만 더 생각해보면 최솟값 이라고 하는 부분에 주목하면 되는 문제이다.

결국 곱셈의 결과가 최소로 나와야 하기 때문에 각 원소별 가장 높은 값을 상쇄시키기 위해 다른 하나의 배열에서는 가장 작은 원소를 뽑으면 되는 문제로 해석할 수 있다.

따라서 그렇게 하기 위해서는
A 에서는 작은 거 순서대로 뽑고 B에서는 큰거 순서대로 뽑아서 곱한 결과 값을 작게(나는 표현하기로 상쇄되도록)해야한다.

🔥 배운것

가끔은 무작정 하는 것보다 그 의미를 드려다 보면 쉽게 해결되는 경우도 많다.
(특히, 정렬을 해볼까? 등등의 아이디어)

🕰️ 시간복잡도

O(nlogn)