프로그래머스 | 최솟값 만들기 [파이썬 python]

프로그래머스

 

처음 시도한 코드

def solution(A,B):
    answer = 0
    for i in range(len(A)):
        a = A.pop(A.index(min(A)))
        b = B.pop(B.index(max(B)))
        answer += a * b
    return answer

두 배열에서 뽑은 각각의 원소의 곱의 누적합이 최소가 되는 경우의 값을 구해야 하는 문제이다.

문제의 예시를 보며 한쪽 리스트에서는 최솟값을 순서대로 고르고, 다른 쪽 리스트에서는 최댓값을 순서대로 고르는 경우가 정답이라고 생각하게 되었다.

그래서 떠오르는 대로 min(), max() 함수를 사용하고, 문제에서 한 번 선택한 원소는 다시 선택할 수 없다고 해 pop() 함수를 사용해 리스트에서 제거해 주었다.

하지만 이 코드를 제출하면 효율성 테스트에서 시간 초과로 실패하게 된다.

for문 안에 index, min, max 함수가 들어있어 시간복잡도가 제곱이 되는 것을 알게 되었다.

그래서 for문 내부의 작업을 단축시키기 위한 방법을 생각해 보며 최종 코드를 작성하게 되었다. 

 

최종 코드

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

for문 안에서 매번 최솟값, 최댓값을 찾는 것보다 사전에 먼저 sort() 함수를 이용해 정렬을 해준 뒤 각각의 원소를 순서대로 접근하였다.

A는 오름차순으로, B는 내림차순으로 정렬하였기 때문에 같은 인덱스 번호를 가지고 크기 순으로 접근할 수 있다.

레벨 2는 확실히 더 효율적인 코드를 만들기 위해 생각을 한번 더 해야 하는 것을 다시 한번 깨달았다!

 

A에서는 최솟값을, B에서는 최댓값을 선택하는 논리가 항상 성립하는지 궁금해서 다른 사람들의 풀이를 많이 찾아보았는데 아래 블로그에서 증명을 해주셔서 확신을 가질 수 있었다.

[알고리즘] 프로그래머스 - 최솟값 만들기