[프로그래머스] Lv2. 구명보트 (파이썬) / Greedy 탐욕법

[문제 링크]

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

프로그래머스

[문제 고민]

• people 리스트를 오름차순으로 정렬해서 가벼운 애부터 태우면 되지 않을까? 라는 논리로 시작
• 1차로 작성한 코드는 실행은 OK but 테스트케이스에서 통과를 주지 않음..

[핵심 개념]

1. 그리디 알고리즘 - 현재 순간만을 고려하여 가장 좋은 선택만 함. 그 선택으로 인한 영향은 생각하지 않는 쿨한 알고리즘..
2. 보통 그래서 '가장 큰 순서' or '가장 작은 순서' 와 같이 정렬이랑 묶이는 경우가 많음. 
3. 한번에 최적으로 태우는 (가장 적은 수의 보트를 사용하는) 방법이란 ? 가장 가벼운애랑 가장 무거운애랑 1묶음으로 묶어서 빼는게 가장 최적임.
4. 그 다음 최적은 가장 무거운 사람을 빼는거임.

[추가 끄적]

1. 실패의 큰 원인: 가장 가벼운애랑 무거운 애를 묶어보는 작업이 없었다.

[실패 코드]  

def solution(people, limit):
    answer = 0 
    people.sort()
    cnt = 0
    sub_limit = limit
    
    for person in people:
        if sub_limit - person >=0:
            answer += 1
            cnt += 1
            sub_limit -= person
            if sub_limit <= 0 and cnt ==2:
                answer -= 1
                cnt = 0
                sub_limit = limit
        else:
            answer += 1
            cnt = 0
            sub_limit = limit
                
    return answer

 

[최종 코드]

def solution(people, limit):
    answer = 0 
    people.sort()
    start = 0 # 가장 가벼운 애
    end = len(people)-1 # 가장 무거운 애
    while start <= end: # 가장 무거운 애부터 시작
        if people[start] + people[end] <= limit: # 가장 가벼운애 + 가장 무거운애 (1묶음)
            start += 1
            end -= 1
        else:
            end -= 1 # 아니면 가장 무거운애
        answer += 1 # 구명보트 추가
    return answer