프로그래머스 고득점 Kit - [구명보트] 해설

고득점 Kit - Greedy(탐욕법)

Lv.2 - 구명보트 해설 코드 공유합니다

python 자료구조를 찾아보니 pop()은 시간복잡도가 O(1)인 반면에, pop(0)은 시간복잡도가 O(n)이더라고요.
pop(0)가 O(n)인 이유는 맨 앞에 있는 요소를 출력 해주기 위해 배열 전체를 복사하기 때문이라고 합니다.

이 때문에 효율성 테스트 첫번째 문제에서 시간초과로 탈락하게 되었습니다.
(물론 그 문제 외에는 깔끔하게 통과합니다.)

아래는 pop(0)를 사용하여 효율성 테스트에서 문제가 생긴 코드입니다.

def solution(people, limit):
    answer = 0
    
    # 오름차순으로 정렬
    arr=sorted(people)
    

    front = 0

    while(len(arr) > 1):
        if(arr[front] + arr[-1] > limit):
            answer += 1
            arr.pop()

        else:
            arr.pop()
            arr.pop(front)
            answer+=1

    if(len(arr) == 1):       
        arr.pop(0)
        answer+=1
        
    
    return answer

따라서 이러한 문제를 해결하기 위해서 list가 아닌 deque를 사용하였습니다.
deque는 맨 앞 요소를 제거하는 시간복잡도가 O(1)이 나옵니다.

다음은 deque를 사용하도록 코드를 수정하여 아주 깔끔하게 효율성 테스트까지 통과한 코드입니다.

from collections import deque


def solution(people, limit):
    answer = 0
    dq = deque()
    
    # 오름차순으로 정렬
    arr=sorted(people)
    
    for i in range(0, len(arr)):
        dq.append(arr[i])

    
    front = 0

    while(len(dq) > 1):
        if(dq[front] + dq[-1] > limit):
            answer += 1
            dq.pop()
        
        else:
            dq.pop()
            dq.popleft()
            answer+=1

    if(len(dq) == 1):       
        dq.popleft()
        answer+=1
        
    
    return answer

풀고나니 매우 기분이 좋군요 ㅎㅎ

결국 deque를 사용하는 것이 효율성 1번 문제의 시간복잡도 문제를 해결하는 핵심이었습니다.

그럼 다음 코드 해설로 돌아오겠습니다. 감사합니다.