[Programmers] L2. 최솟값 만들기 (Python)

---

[문제 링크] 👇

프로그래머스

---

풀이 방법

💡 A 리스트의 최소와 B 리스트의 최대의 곱, sort() 사용

 

A 리스트는 오름차순 정렬, B 리스트는 내림차순 정렬한다.

 

오름차순 정렬

A.sort()

 

내림차순 정렬

B.sort(reverse=True)

 

리스트의 길이만큼 반복문을 돌려 연산을 한다.

 

Solution

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

 

 

👩‍💻 회고

초기 코드(정확성 O, 효율성 X)

def solution(A,B):
    answer = 0
    A = sorted(A)
    B = sorted(B) # 정렬

    for i in range(len(A)):
        if min(A, B) == A:  # 최소값이 A 리스트에 있을 경우
            answer += A.pop(0) * B.pop()  # 최소값인 맨 앞 요소, 최댓갑인 맨 뒤 요소 꺼낸 후 연산
        else:  # 최소값이 B 리스트에 있을 경우
            answer += A.pop() * B.pop(0)

    return answer

 

효율성 테스트 실패의 원인

반복문 안에서 pop(0)을 사용해 리스트의 첫 번째 요소를 제거하고 있기 때문이다. pop(0)은 리스트 전체를 한 칸씩 이동시키므로 시간복잡도가 O(n)이 되어, 입력 크기가 클 때 비효율적이다.

 

두 리스트 중에 최소값이 들어가 있는 기준으로 연산을 해야 하는 건 줄 알았는데, 사실 어떻게 하든 똑같은 결과를 낸다.

그래서 굳이 min() 함수나, pop() 함수를 사용할 필요가 없었다. 단순히 정렬을 어떻게 하느냐가 중요한 문제였다.

 

---