[프로그래머스/Python] Lv. 2 최솟값 만들기

안녕하세요.

이번 문제는 "최솟값 만들기" 입니다.

 

문제 링크

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

프로그래머스

 

문제 요약

배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱하고, 곱한 값을 누적하여 더합니다.

이때최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다.

결론 : 배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 작성하는 것입니다.

 

문제 풀이

🔍 제가 생각한 풀이 방법을 설명하자면,

1. 두 배열에서 각각 최댓값을 구한다.

2. 두 최댓값 중에 더 큰 최댓값(Max)을 가린다.

3. 최댓값이 선택되지 않은 배열에서 최솟값(Min)을 구해서 Max * Min 을 한다.

4. 곱하기를 한 값은 이미 사용된 값이므로 리스트에서 제거한다.

 

- 위 과정을 for문을 통해 반복하여 "누적된 최솟값"을 구한다.

 

✋ 여기서 잠깐!

처음에 min, max 함수를 이용해서 문제를 풀었는데 정확성은 모두 통과를 했지만, 효율성 테스트에서 시간 초과가 나고 말았습니다.

질문하기를 통해 알게된 사실이 max, min 함수는 시간복잡도가 O(n)이기 때문이었습니다.

그래서 그 부분을 시간복잡도가 O(nlogn)인 정렬함수 sort()를 이용하여 풀었더니 해결되었습니다.

 

전체 코드

def solution(A,B):
    answer = 0
    add = 0
    A.sort()
    B.sort()
    
    for i in range(len(A)):
        if A[-1] > B[-1]:
            add = A[-1] * B[0]
            A.pop()
            B.pop(0)
        else:
            add = B[-1] * A[0]
            B.pop()
            A.pop(0)
        answer += add

    return answer