[알고리즘] 프로그래머스_구현_구명보트_코드주석

'프로그래머스 코딩테스트 문제 풀이 전략: 파이썬편'으로 알고리즘을 공부하고 있다. 직접 풀지 못한 문제들은 책의 풀이를 이해하고, 주석을 달면서 공부 중이다.

오늘 푼 문제는 구명보트 문제이다.

🔹 ch.12 구현
🔹 탐욕알고리즘

💻 코드

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

    a = 0
    b = len(people) - 1 
    # len(people) = 4, b = 3 # a와 b가 투 포인터
    
    while a < b : # a가 왼쪽 포인터, b가 오른쪽 포인터이므로 
    			  # a가 b를 넘어서 가지 않도록 조치 필요
    			  # 그래서 같으면 안 된다
        
        if people[b] + people[a] <= limit : 
        # people [50, 50, 70, 80], 
        # people[a] = people[0](=50), people[b] = people[3](=80)
        # if 50 + 80 <= 100:
            
            a += 1                          
            answer += 1
            # 조건을 만족하면 a의 위치를 오른쪽으로 한칸 이동하고 
            # b도 이동하지만(+ answer에도 1추가)
            # 조건 만족하지 않으면 a는 위치 고정, b만 왼쪽으로 이동
        b -= 1
        
        # a = 0, b = 3, 50, 80
        # a = 0, b = 2, 50, 70
        # a = 0, b = 1, 50, 50 
        # 그럼 a = 1, answer = 1, b = 0
        # while문에서 a < b 조건을 만족하지 않으므로 while문 종료 

    return len(people) - answer 
    # answer에 담기는 숫자들은 2명이 짝을 이루어 
    # 구명보트를 같이 탈 수 있는 경우의 수이다. 
    
    # people [50, 50, 70, 80] 예시에서는 
    # 50, 50 두 사람이 보트를 같이 탈 수 있으므로 
    # 남은 70, 80은 각각 보트 하나씩 탄다고 생각할 수 있다. 
    # 그럼 답은 3인데
                                
    # 2명이 하나로 묶여 answer의 경우의 수 1로 생각되므로, 
    # len(people) - answer를 하면 남은 사람들이 
    # 한 사람당 한 보트를 이용하는 경우의 수까지를 
    # 같이 구할 수 있는 것 같다.  

📌 출처: '프로그래머스 코딩테스트 문제 풀이 전략: 파이썬편', 김범수, 길벗