[알고리즘 문제 풀이] - 최솟값 만들기

요즘은 시간 날때마다 알고리즘 문제를 하나씩 풀고 있는데요.

 

프로그래머스에 있는 최솟값 만들기 문제를 풀어 봤습니다.

 

 

"두개의 주어진 리스트에서 각각 한개씩 뽑아 두 수를 곱한 값을 더했을때 최솟값을 찾아라"

 

언뜻 보면 굉장히 골치 아픈 문제 같아 보입니다.

 

더할수 있는 모든 경우의 수를 찾아야 되나?

 

처음 봤을때 이런 생각 하신 분들 많을것 같아요.

 

곱했을때 

 

<생각의 과정>

 

1. 곱했을때 최소값을 만드려면 어떻게 해야 될까?

 

2. 첫번째 리스트에서 가장 작은 숫자와 두번째 리스트에서 가장 큰 숫자를 곱하면 최소값을 만들수 있다.

 

3. 마찬가지로 첫번째 리스트에서 가장 큰 숫자가 나온다면 두번째 리스트에서는 당연히 가장 작은 숫자가 나와야 함

 

 

<풀이>

def solution(A,B):
    answer = 0
    A.sort()
    B.sort(reverse=True)
    for x,y in zip(A,B):
        answer += x*y
    return answer

 

해석이 필요할까 싶을 정도로 코드는 간단합니다.

 

저는 A 리스트를 오름차순으로 정렬하고 B 리스트를 내림차순으로 정렬 했습니다.

 

이건 반대로 B를 오름차순으로 정렬하고 A를 내림차순으로 정렬해도 상관 없습니다.

 

파이썬에서 리스트를 정렬하는 대표적인 함수가 sort()와 sorted()인데

 

저는 속도가 더 빠른 sort()를 썼습니다.

 

만약 리스트가 아니라면 sort()를 쓸수 없으니 sorted()를 쓰면 되겠네요.

 

그 후에는 각 리스트에서 숫자를 하나씩 뽑아서 곱하고

 

더했습니다.

 

결과는

 

 

예상대로 정확성 테스트는 모두 통과를 했네요.

 

사실 이 문제는 edge case라고 할만한게 딱히 없어서 큰 위기는 없었습니다.

 

대신 효율성이 중요한 문제 였는데

 

안정적으로 통과가 됐네요.