[파이썬] 프로그래머스 구명보트 풀이

문제 확인

프로그래머스

나의 풀이

• 한 번에 최대 2명을 태울 수 있기 때문에, 최적의 구성은 무거운 사람 + 가벼운 사람을 태울 경우다.
• 무거운 사람, 가벼운 사람의 무게 합이 제한 무게를 넘는지 확인하기 위해서, 무게 순으로 people을 정렬 했다.
• 정렬 뒤엔 시작 점과 끝 점을 비교하기 위해서 투 포인터를 활용했다.

# 한 번에 최대 2명
# 최적 -> 무거운 사람 + 가벼운 사람
def solution(people, limit):
    people.sort()
    answer = 0
    # 투포인터 시작 - 끝 점
    start, end = 0, len(people) - 1
    # 동일할 때 까지 시행
    while start <= end:
        # 2명 다 태울 수 있는 경우
        if people[start] + people[end] <= limit:
            start += 1
        end -= 1
        answer += 1
    return answer

다른 사람 풀이

• 사람들을 보트에 태우는 것은 deque를 사용해 popleft()와 pop()을 하는 것과 동일하다.

from collections import deque

def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    q = deque(people)
    
    while q:
        if len(q)>1:
            if q[0]+q[-1] <= limit:
                q.pop()
                q.popleft()
                answer+=1
            else:
                q.popleft()
                answer+=1
        else:
            q.pop()
            answer+=1

    return answer

 

[프로그래머스] 구명보트 / Python / Level 2