구명보트

프로그래머스

이 문제는 스택으로 다음과 같이 풀면

def solution(people, limit):
    people.sort(reverse=True)
    cnt = 0
    while len(people) >= 2:
        if people[0] + people[-1] <= limit:
            people.pop()
            people.pop(0)
            cnt += 1
        else:
            people.pop(0)
            cnt += 1
    cnt += len(people)
    return cnt

효율성에서 시간초과가 뜬다.

아래와 같은 방법을 찾았는데 정렬한 다음 인덱스를 이용해서 가장 무거운, 가장 가벼운것의 합이 limit보다 작거나 같으면 둘 다 탑승하고 인덱스를 둘 다 이동한다.
만약 limit보다 크다면 무거운 것만 탑승하고 가벼운 건 그대로 있는다.

구현은 어렵지 않으니 방법이 중요한 것 같다.

def solution(people, limit):
    cnt = 0
    
    people.sort(reverse=True)
    i = 0
    j = len(people)-1
    
    while i<=j:
        if people[i]+people[j]<=limit:
            j -= 1
        i += 1
        cnt += 1
        
    return cnt

def solution(people, limit):
    people.sort(reverse=True)
    cnt = 0
    i = 0
    j = len(people)-1
    
    while i <= j:
        if people[i] + people[j] <= limit:
            i += 1
            j -= 1
            cnt += 1
        else:
            i += 1
            cnt += 1
    return cnt