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

문제 설명

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
• A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수
• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

입출력 예

입출력 예

 

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
A에서 첫번째 숫자인 1, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 4) 다음, A에서 두번째 숫자인 2, B에서 첫번째 숫자인 3을 뽑아 곱하여 더합니다. (누적된 값 : 4 + 6 = 10)
이 경우가 최소이므로 10을 return 합니다.

---

나의 풀이

첫 번째 시도

from itertools import permutations
def solution(A,B):
    answer = float('inf') # 가장 큰 수
    table = [[A[i] * B[j] for i in range(len(A))] for j in range(len(A))]
    routes = list(permutations(list(range(len(A))), len(A)))

    for route in routes:
        mid = sum([table[i][r] for i, r in enumerate(route)])
        answer = min(answer, mid)
    return answer

* float('inf')는 파이썬에서 가장 큰 수를 뜻한다. 무한을 나타낼 때 유용하게 사용할 수 있다.

우선 A와 B의 각 요소를 곱한 테이블을 만든다.

예를 들어 A가 [1, 4, 2], B가 [5, 4, 4] 일 때 만들어지는 테이블은 다음과 같다.

x	1	4	2
5	5	20	10
4	4	16	8
4	4	16	8

그리고 routes를 만드는데 routes는 어떤 경로로 더할지 미리 정의한 리스트이다.

예를 들어 위와 같이 크기가 3인 리스트인 경우에 만들어지는 routes는 다음과 같다.

routes

예를 들어 경로가 두 번째에 있는 (0, 2, 1)일 경우 테이블에서 0번 열, 2번 열, 1번 열의 값을 더하는 것이다.

(5 + 8 + 16)

이렇게 모든 routes를 돌아보고 최소값을 찾는 아이디어로 코드를 짰다.

 

그 결과는...

첫 번째 테스트 결과

아주 처참했다. 답은 맞는데 시간이 너무 오래걸리는 모양이다.

그럴법도 한 것이 A, B의 크기가 1000 이하이기 때문에 최대 1000000 크기의 테이블이 만들어지며 1000! (factorial) 만큼의 route가 만들어져 최대 1000 * 1000 * 1000! 만큼의 경우의 수가 발생한다.

그래서 테스트 중 어떤 경로일 때 최소값을 갖는지 궁금하여 print로 route를 찍어보았다.

from itertools import permutations
def solution(A,B):
    ...
    for route in routes:
        mid = sum([table[i][r] for i, r in enumerate(route)])
        if answer > mid: print(route)
        answer = min(answer, mid)
    return answer

if answer > mid: print(route) 부분을 보면 계산한 중간 값인 mid가 현재까지 가장 작았던 answer보다 작으면 answer이 mid로 교체가 발생하는데 이때의 route를 print로 찍어보았다.

그 전에 추가 테스트 케이스로 더 큰 크기의 리스트 A, B를 정의했고, A와 B의 요소들은 오름차순으로 정렬된 상태로 테스트 케이스를 추가했다.

그랬더니 놀라운 사실을 발견했다.

처음에 추가한 테스트 케이스

두 번째에 추가한 테스트 케이스

내림차순으로 정렬된 형태가 나왔다. 이 사실을 바탕으로 두 번째 시도를 하였다.

 

두 번째 시도

def solution(A,B):
    A.sort(); B.sort()
    table = [[A[i] * B[j] for i in range(len(A))] for j in range(len(A))]
    return sum([table[i][r] for i, r in enumerate(range(len(A)-1, -1, -1))])

A와 B를 sort 메소드로 오름차순 정렬하였다.

이후 위와 동일하게 table을 만들고 예를 들어 A의 크기가 4라면 (3, 2, 1, 0)을 차례로 더했다. 코드 양이 획기적으로 줄었다. (코드 양이 전부는 아니겠지만...)

그 결과는...

두 번째 테스트 결과

 

What....?? 얼마나 효율성을 높여야 하는가...

세 번째 시도 (성공)

맞다. 테이블을 만드는 것 자체도 리소스를 많이 잡아먹는다. 아까 얘기했듯이 최대 1000 * 1000 크기의 테이블을 만들어야하기 때문에 이 부분에서도 리소스를 절약할 수 있다. (그때 그때 직접 곱하면 된다)

def solution(A,B):
    A.sort(); B.sort()
    return sum([A[i] * B[r] for i, r in enumerate(range(len(A)-1, -1, -1))])

테이블을 만드는 과정을 없애고, 직접 A[i] 와 B[r]을 곱했다.

위 코드에서 range의 범위 지정이 너무 지저분하기 때문에 좀 더 생각을 해봤다.

A와 B 둘 중 하나를 내림차순으로 변경하면 (3, 2, 1, 0) 이 아니라 (0, 1, 2, 3)이 되어서 훨씬 깔끔해진다.

그렇게 정리한 코드는 다음과 같다.

def solution(A,B):
    A.sort(reverse=True); B.sort()
    return sum([A[i] * B[r] for i, r in enumerate(range(len(A)))])

여기서 zip 함수를 사용한다면 1줄로도 줄일 수 있을 듯 하지만... 여기서 그치도록 하겠다.

세 번째 테스트 결과

 

오늘도 최적화의 중요성을 깨닫는다.

 

근데 1점 주는거 실화...? 기준이 뭔지..