[프로그래머스] 구명보트 (그리디)

사용 언어: Python3

문제

구명보트

풀이

deque 이용

from collections import deque # ✅

N, M = map(int, input().split())
lst = list(map(int, input().split()))
lst.sort()
lst = deque(lst) # ✅ 리스트를 deque 자료구조로 변환

cnt = 0
while lst: # 가장 무거운 사람부터 탈출시키는데, 가벼운 사람까지 같이 탈 수 있으면 태운다고 생각
    if len(lst) == 1: # ✅ 예외 처리 꼼꼼히 (lst의 값이 하나일 때에는 0번째 원소와 -1번째 원소가 같은 값이기 때문에 논리 오류 발생 방지)
        cnt += 1
        break
    if lst[0] + lst[-1] <= M:
        lst.popleft() # 가장 가벼운 사람까지 탑승
    lst.pop() # 가장 무거운 사람 탑승
    cnt += 1
print(cnt)

• 정답!

투 포인터

def solution(people, limit):
    cnt = 0
    lt, rt = 0, len(people)-1
    people.sort()
    while lt < rt:
        if people[lt] + people[rt] <= limit:
            cnt += 1 # 두 명씩 탑승한 보트 수
            lt += 1
        rt -= 1
    
    return len(people) - cnt

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기