프로그래머스 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간 초과 (효율성 테스트 시간초과)

def solution(people, limit):

    answer = 0

    from collections import deque

    people.sort()

    people = deque(people)

    while people:
        
        p1 = people.popleft()
        
        try:
            
            tmp = deque([])
            while people:
                p2 = people.pop()

                if p1+p2<=limit:
                    break
                else:
                    tmp.appendleft(p2)
            people += tmp

        except:
            pass

        answer += 1

    return answer

2명씩 탑승할 수 있는 구명보트에 limit 무게를 초과하지 않게끔 하여 최소한으로 모든 사람들을 태울 수 있는 구명보트 수를 구하는 문제입니다.

최소 몸무게 리스트를 정렬한 뒤 최저 몸무게와 최대 몸무게를 연산하여 limit을 넘지 않을 시 두명을 한 구명보트에 탑승시켰습니다. 이때 limit 무게를 초과할 시 2번째, 3번째 최대 몸무게들을 연산하여 확인하는 방식입니다.🍒🍒🍒

위 코드대로 구현은 가능하지만 효율성 테스트 케이스에서 시간 초과가 나서 다른 풀이를 참고했습니다.

[다른 사람의 풀이1]

from bisect import bisect_right
from collections import deque

def solution(people, limit):
    people.sort()
    time =0
    people = deque(people)
    while people:

        first = people.pop()
        left = limit-first

        if people and left>=people[0]:
            
            if piv := bisect_right(people,left):

                del people[piv-1]
        time +=1
    return time

정렬된 몸무게 리스트에서 최대 몸무게와의 합이 limit를 넘지않는 몸무게를 이분 탐색으로 찾아
함께 탑승시키는 방법입니다.🐷🐷🐷

저의 풀이에서는 2중 while을 통해 몸무게 조합을 구하였다면 위 코드는 while안의 이분탐색을 통해 시간복잡도를 줄여 해결한 풀이입니다.

[다른 사람의 풀이2]

def solution(people, limit) :
    answer = 0
    people.sort()

    a = 0
    b = len(people) - 1
    while a < b :
        if people[b] + people[a] <= limit :
            a += 1
            answer += 1
        b -= 1
    return len(people) - answer
    

몸무게 리스트의 양 끝단 투 포인터를 지정하여 구현한 풀이입니다. 이 풀이를 보고 본 문제를 풀어낼 때 너무 어렵게 생각했구나라고 깨닫게 되었습니다.

저의 풀이에서 2중 while으로 구현한 이유는 limit을 초과하지 않고 빈공간이 최소화된 최적의 몸무게 조합을 구하기 위함이였습니다. 하지만 정렬된 몸무게 리스트에서 최적의 몸무게 조합과 상관없이 한 구명보트에는 최대2명만 탑승하기 때문에 limit 초과 유무만 판단해주면 되는 문제임을 알게 되었습니다.🐻🐻🐻

감사합니다.