프로그래머스 Lv2 구명보트

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=python3 

프로그래머스

 

 

 

풀이

해당 문제는 사람과 무게 제한이 주어질 때, 구출하기 위해 필요한 구명보트의 최소수를 구하는 문제이다.

 

문제 카테고리가 탐욕법이기도 하고, 이런 문제류는 높은 무게부터 시작하여 처리해 나가면 쉽게 풀리는 문제라고 판단되었다. 그래서 다음과 같은 과정을 생각하고 문제를 풀기 시작했다.

 

    1. people을 내림차순으로 정리한 후 앞 요소와 맨 뒷 요소를 더한 값이 limit 넘는지 체크
    2. limit 넘으면 앞 요소만 제거한 후 answer 값을 + 1
    3. limit을 넘지 않으면 앞, 뒤 요소 모두 제거한 후 answer 값을 + 1

 

def solution(people: list, limit: int) -> int:
    """
    1. people을 내림차순으로 정리한 후 앞 요소와 맨 뒷 요소를 더한 값이 limit 넘는지 체크
    2. limit 넘으면 앞 요소만 제거한 후 answer 값을 + 1
    3. limit 을 넘지 않으면 앞, 뒤 요소 모두 제거한 후 answer 값을 + 1
    """
    answer: int = 0
    people_copy: list = sorted(people.copy(), key=lambda x: -x)

    while people_copy:
        # 제일 특별한 경우 people_copy의 길이가 1일 때 예외처리
        if len(people_copy) == 1:
            answer += 1
            k = people_copy.pop(0)
        else:
            if people_copy[0] + people_copy[-1] <= limit:
                k = people_copy.pop(0)
                k1 = people_copy.pop(-1)
                answer += 1
            else:
                k = people_copy.pop(0)
                answer += 1

    
    return answer

 

 

하지만 효율성 테스트에서는 모두 실패를 했다. 사실 해당 문제를 보자마자 든 생각을 바로 코드에 옮겼기에 효율성을 생각하지 못하고 짠 코드였는데, 바로 효율성 테스트에서 실패하는 것을 보고 좀 더 신중히 생각하는 태도를 가져야겠다는 경각심이 생겼다. 

 

곰곰이 코드를 살펴보니, 해당 문제에서 효율성을 고칠만한 부분은 people_copy.pop(0) 부분을 deque으로 바꿔서 popleft을 이용하는 것 정도가 있을 것 같아서 from collections import deque을 이용하여 덱을 가져온 뒤 코드를 수정하였다. 

 

from collections import deque

def solution(people: list, limit: int) -> int:
    """
    1. people을 내림차순으로 정리한 후 앞 요소와 맨 뒷 요소를 더한 값이 limit 넘는지 체크
    2. limit 넘으면 앞 요소만 제거한 후 answer 값을 + 1
    3. limit 을 넘지 않으면 앞, 뒤 요소 모두 제거한 후 answer 값을 + 1
    """
    answer: int = 0
    people_copy: deque = deque(sorted(people.copy(), key=lambda x: -x))

    while people_copy:
        if len(people_copy) == 1:
            answer += 1
            people_copy.popleft()
        else:
            if people_copy[0] + people_copy[-1] <= limit:
                people_copy.popleft()
                people_copy.pop()
                answer += 1
            else:
                people_copy.popleft()
                answer += 1

    
    return answer

 

 

 

 

 

list.pop(0) vs deque.leftpop()

자 그럼 왜 list.pop(0)을 쓰지 않고 deque.leftpop()을 이용하는 게 효율성 면에서 더 좋은 이유에 대해 알아보자.

 

일반적으로 리스트의 마지막 원소를 삭제는 O(1)이지만, 아래 그림처럼 첫 번째 원소를 삭제하면 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)이 된다.

 

https://wellsw.tistory.com/122

그와 반대로 deque의 구조는 내부적으로 double linked list로 구현되어 있기 때문에 양 끝의 요소에 대한 추가/삭제에 걸리는 시간 복잡도가 O(1)이 된다.

https://wellsw.tistory.com/122

∴결론 : 따라서 양 끝의 요소에 추가/삭제가 빈번하게 일어나는 상황이라면 list보다는 deque을 이용하여 로직을 구현하는 것이 효율성 면에서 좋은 코드를 작성할 수 있을 것이다. 

 

 

 

 

---

참조

 

https://wellsw.tistory.com/122

[파이썬] 덱 vs 리스트 속도 차이? (deque vs list speed 차이)