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

def solution(people, limit):
    boat = []
    people.sort()

    light = people[0]
    idx = 0
    
    for i in range(len(people)-1, -1, -1):
        if idx > i:
            break
        person = people[i]
        if person + light > limit:
            # 가장 가벼운 사람이랑도 못앉으면 혼자 가야지
            boat.append(person)
            continue
        # 가장 가벼운 사람이랑은 같이 앉아갈 수 있다! 그럼 앉아가슈
        if idx < i:
            boat.append(person + light)
            idx += 1
            light = people[idx]
            continue
        # 앉아갈 짝이 없으면 혼자 가렴
        boat.append(person)
    return len(boat)

구명보트 개수가 최소가 되려면 무조건 가장 무거운 사람을 제거해야한다는 사실을 깨달으면 쉬운 문제다!

가장 무거운 사람을 제거하려면? 가장 가벼운 사람과 같이 앉아가게 하면 된다!

 

그냥 그리디 문제로만 알고 풀었는데 알고보니 투포인터 문제라고 하더라!

내 풀이도 어쩌다 보니 포인터를 두개 쓰고 있긴 하다..! (i와 idx)

 

시간 복잡도

for문: O(n)

=> O(n)

 

다른 사람 풀이

- 구명 보트의 개수를 직접 구하지 않고, 커플(같이 앉아가는)의 수 만큼 전체 인원에서 빼주면 된다!

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 # 전체에서 두명이서 앉아가는 배의 숫자만큼을 빼줌