시간을 줄이는 효율적인 코딩하기

1. 문제

 

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

코딩테스트 연습 - 최솟값 만들기

 

 

길이가 같은 배열 A,B 두개가 있습니다.

 

각 배열은 자연수로 이루어져 있습니다.

 

배열 A,B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다.

 

이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다.

 

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

 

단 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.

 

 

 

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

 

 

2. 제한사항

 

배열 A,B의 크기는 1000이하의 자연수

 

배열 A,B의 원소의 크기는 1000이하의 자연수

 

 

3. 예시

 

 

 

4. 나의 풀이

 

탐욕법을 생각해서 누적 합이 최소일려면 최솟값끼리 뽑아서 곱한다음에 더해가야한다고 생각을 했음

 

def solution(A,B):
    
    answer = 0
    
    while len(A) != 0:
        
        a = A.pop(A.index(min(A)))
        b = B.pop(B.index(min(B)))
        
        answer += a*b
        
    return answer

 

이러면 예시도 통과를 못하더라… 왜 통과를 못했나 생각을 해봤지

 

A=[1,4,2], B=[5,4,4]라고 한다면

 

A에서 1을 뽑고 B에서 4를 뽑고 곱한다면 4

 

A에서 2를 뽑고 B에서 4를 뽑고 곱하면 8

 

A에서 4를 뽑고 B에서 5를 뽑아서 곱하면 20

 

최솟값끼리 뽑으면 마지막처럼 A의 max와 B의 max가 곱해져서 최대가 된단 말이야

 

그래서 순간적인 기지로

 

A에서는 min을 뽑고 B에서는 max를 뽑아서 곱한다음에 더한다면..?

 

결국 A가 커질수록 B는 작아지고, A가 작을수록 B는 커져서 곱한 값이 작아질거라고 생각을 했음

 

 

정확성 테스트는 전부 통과하는데 효율성 테스트를 통과못함…

 

def solution(A,B):
    
    answer = 0
    
    while len(A) != 0:
        
        a = A.pop(A.index(min(A)))
        b = B.pop(B.index(max(B)))
        
        answer += a*b
        
    return answer

 

그러면 어떤 부분에서 시간을 잡아먹었을까… 그동안 공부한걸 토대로 생각해본다면

 

while len(A) != 0:에서 매회 반복마다 A의 길이를 구해야하니까

 

A의 길이만큼 시간 복잡도가 들어가서 길이가 길어질수록 오래걸림

 

그러면 A의 길이를 미리 구한다음에 반복문이 돌아갈때마다 1을 빼는 방식으로 바꿈

 

def solution(A,B):
    
    answer = 0
    
    len_a = len(A)
    
    while len_a != 0:
        
        a = A.pop(A.index(min(A)))
        b = B.pop(B.index(max(B)))
        
        answer += a*b
        
        len_a -= 1
        
    return answer

 

물론 이래도 시간을 완벽하게 줄이지는 못함..

 

정확성 테스트 통과시간 봤는데 큰 차이는 없더라

 

그러면 더 줄일 수 있는 방법은..?

 

시간이 들어가는 요소는 A.index(min(A))에서

 

min(A)에서 A의 길이만큼 검사해서 min을 구해야하고

 

A.index()에서 해당 원소의 index를 찾기 위해 길이만큼 검사해야함

 

이걸 두번이나 하니까 시간이 상당히 들어갈거임

 

순간적인 기지로… A와 B를 sort한다음에 왼쪽부터 빼나간다면 어떨까?

 

그러면 검사하는 작업을 거치지 않아도 되니까 시간이 상당히 줄어들거다

 

def solution(A,B):
    
    answer = 0
    
    len_a = len(A)
    
    A.sort()
    B.sort(reverse=True)
    
    while len_a != 0:
        
        a = A.pop(0)
        b = B.pop(0)
        
        answer += a*b
        
        len_a -= 1
        
    return answer

 

A를 오름차순 sort하고 B를 내림차순 sort한다음에 0번째 원소를 뽑으면

 

A는 최솟값부터 뽑히고 B는 최댓값부터 뽑힐거임

 

 

예상대로 효율성 테스트 통과

 

 

5. 다른 풀이

 

이 문제의 핵심은 결국 한쪽에서는 최솟값을 뽑고 다른 쪽에서는 최댓값을 뽑아서 곱한 다음에 더해나가는거다

 

def solution(A,B):

    return sum(a*b for a,b in zip(sorted(A),sorted(B,reverse=True)))

 

sum안에서 comprehension을 해버리네..

 

 

6. 되돌아보기

 

탐욕법의 핵심을 결국 파악한 것이 좋았다

 

최솟값을 한쪽에서 뽑고 다른 쪽에선 최댓값을 뽑아 곱한 다음에 더해나가야 누적합이 최소가 된다

 

시간을 줄이기 위해서 여러가지 시도를 한 것이 좋았다

 

len()을 쓰지 않고 반복문 밖에서 len을 미리 계산 한 다음에 하나씩 빼나감

 

index()나 min(), max()를 쓰지 않고 pop을 하는 방법을 기억해야한다

 

반복문 밖에서 미리 list를 sort하고

 

오름차순 sort하면 0번째 원소부터 pop(0)하면 최솟값부터 뽑힐거고

 

내림차순 sort하면 0번째 원소부터 pop(0)하면 최댓값부터 뽑힐거임

 

확실히 공부한 효과가 있는 것 같긴하다… 예전 같았으면 풀지도 못했을듯