Lv2. 구명보트

문제 보기 :  구명보트

프로그래머스

 

---

문제

• 정답률 : 70%

---

작성 코드

from collections import deque
def solution(people, limit):
    
    people = deque(sorted(people))
    answer = 0
    s = 0 ; e = -1
    
    while len(people) > 1:
        if people[s] + people[e] > limit:
            people.pop()
        else:
            people.popleft()
            people.pop()
        answer += 1
        
    if people:
        return answer + 1
    else:
        return answer

---

풀이

큐를 이용해서 풀이했다. 처음에는 인원 수에 상관없이 limit에 가까이 가도록 사람들을 묶어야하는 것으로 이해했다.
근데 무조건 최대 2명씩만 묶을 수 있고, limit을 넘기면 안되는 것이었다.

리스트 + heapq로 풀려고 했는데, 뒤이어 작성하는 while문 속에서 remove를 사용할 수 밖에 없는데, 그럼 시간복잡도가 O(N²)가 되어 효율성 테스트에서 시간초과가 발생했다.

그래서 찾아낸 방법은 deque였다.
여러번 시행착오 끝에 규칙을 찾았는데 항상 최댓값과 최솟값을 더해 limit과의 대소관계를 비교한다는 것이다.
최댓값, 최솟값은 deque에 입력하기 전 리스트 정렬, 맨 앞 맨 뒤 원소로 찾았다.
최댓값+최솟값 > limit이면 최댓값만 pop으로 제거한다. 아니라면 최대, 최소 모두 pop, popleft로 제거한다.

while문이 끝난 뒤 people에 원소가 남아있다면 answer + 1을 답으로 출력하고, 없다면 answer을 답으로 출력한다.