[프로그래머스 lv 2] 구명보트

사용 언어 - Python3

문제 - 구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

 

 

정답

덱

리스트의 pop, append 이용

 

1. 정렬후 스택 사용하기 => 절반 테스트케이스에서 오답

def solution(people, limit):
    answer = 1
    stack = []
    people.sort()
    for p in people:
        if len(stack) == 2: # 이미 최대 두명 태웠다면
            answer += 1 # 보트개수 추가
            stack = [] # 리셋
        
        while stack and len(stack) < 2 and stack[-1] + p > limit: # 한 보트에 안담김
            answer += 1 # 앞사람 혼자 보트태움
            stack.pop()
            
        stack.append(p)
    return answer

 

2. deque 사용하기

최대 두명씩밖에 탈 수 없기 때문에, 가장 적게 구명보트를 사용하려면

가장 무거운 사람 + 가장 가벼운 사람을 같이 태울 수 있는지 확인한다!

먼저, 내림차순 정렬 후, stack[0]과 stack[-1] 을 동시에 태울 수 있는 지 확인한다.

조건 만족시 answer += 1, stack에서 둘다 삭제한다.

같이 태울 수 없다면 둘 중 더 큰 값만 삭제한다.

from collections import deque

def solution(people, limit):
    answer = 0
    stack = deque(sorted(people,reverse=True)) # 내림차순 정렬
    
    while len(stack) > 1:
        if stack[0] + stack[-1] <= limit:
            answer += 1 # 같이 보트태우고 둘다 pop
            stack.pop()
            stack.popleft()
        else:
            answer += 1
            stack.popleft() # 더 큰 것만 없애기
    if stack: # 남아있는 사람 한명 있다면 보트태우기
        answer += 1

    return answer

 

 

 

 

레퍼런스

https://velog.io/@sem/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LEVEL2-%EA%B5%AC%EB%AA%85%EB%B3%B4%ED%8A%B8-Python

[프로그래머스] LEVEL2 구명보트 (Python)