프로그래머스 | 탐욕법 | 구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=python3

프로그래머스

 

시도 1 기존 코드 - 시간 초과

모든 조합을 고려해야 하나 했지만 (combination),,, 시간 초과가 나와버림

from itertools import combinations
def solution(people, limit):
    answer = 0
    
    processed_pp = []
    for boat in combinations(people,2):
        boat_weight = 0
        for i, b in enumerate(boat):
            if i in processed_pp:
                continue
            boat_weight += b
        if boat_weight > limit:
            continue
        else:
            answer += 1
            for i, p in enumerate(people):
                if p in boat:
                    processed_pp.append(people[i])
                    
    # print(processed_pp)
    if processed_pp != people:
        answer += len(people) - len(processed_pp)
    
    return answer

 

시도2 투포인터 알고리즘 학습 

def solution(people, limit):
    people.sort()
    
    answer = 0
    left, right = 0, len(people) - 1
    
    while left < right:
        if people[left] + people[right] == limit:
            left += 1; right -= 1; answer += 1
        elif people[left] + people[right] < limit:
            left += 1
        else:
            right -= 1
    
    answer += len(people) - answer*2
    return answer

 

시도 3

무거운 것과 가벼운 것을 양끝으로 배분할 수 있도록 sort 정렬

def solution(people, limit):
    people.sort()  # 몸무게 오름차순 정렬
    left, right = 0, len(people) - 1
    answer = 0

    while left <= right:
        # 가장 가벼운 사람 + 가장 무거운 사람을 태워본다
        if people[left] + people[right] <= limit:
            left += 1  # 둘 다 태움
        right -= 1   # 무거운 사람은 반드시 태워야 함
        answer += 1  # 보트 1척 사용

    return answer