[프로그래머스/42885/level2/고득점kit] 구명보트 - 그리디, 두 포인터 사용

문제

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

• 2명이서 갈수있는 사람들을 제거하고 -> 나머지는 1인 1보트로 count
• 젤 가벼운 사람부터 -> 무거운 순으로 짝을 매칭

내 풀이 - 정확성 통과 / 시간초과 3개

• 이유 : 경우의 수만 구하면되기 때문에, 굳이 스택에서 pop으로 원소를 제거하지 않아도되는데, 굳이 제거해서 시간이 더 들었다.

def solution(people, limit):
    answer = 0
    
    people.sort(reverse=True)
    while people:
        k = 0

        while k - len(people) < -1:
            if people[-1] + people[k] <= limit:
                people.pop()
                people.pop(k)
                answer += 1
                break
            else:
                k += 1
        else:
            break

    #짝이 없으면 혼자 보트탐
    return answer + len(people)

수정한 풀이

• 두 포인터 이용 - 쌍이 매칭되면 시작점과 끝점을 줄여서 다시 시작하면 됨 = pop을 안써도된다

def solution(people, limit):
    answer = 0
    
    people.sort()
    s = 0
    e = len(people) - 1
    
    while s < e:
        if people[s] + people[e] <= limit:
            answer += 1
            s += 1
        e -= 1
    

    # answer + (len(people) - 2 * answer)
    return len(people) - answer