[그리디] 프로그래머스 Lv2. 구명보트 - Python

🗂️ 문제

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

프로그래머스

 

💡 접근법

투 포인터를 사용하여 리스트의 인덱스에 접근했다.

 

while문을 통해 i≤r일 때만 반복문을 수행한다.

투 포인터의 이동 원칙은 다음과 같다.

1. people[l] + people[r] ≤ limit: l += 1 , r -= 1
2. people[l] + people[r] > limit: r -= 1

이때 l==r이면 r-=1을 수행한다.

 

예시를 통해 자세히 살펴보자.

 

people = [30, 60, 70, 50], limit = 100

1. 먼저 졍렬을 수행한다. people = [30, 50, 60, 70]
2. l = 0, r = 3일 때, people[0] + people[3] ≤ limit을 만족한다. 따라서 30kg인 사람과 70kg인 사람을 하나의 보트에 태울 수 있다. 다음 비교를 위해 l을 1 증가시키고 r을 1 감소시킨다. 즉, answer = 1, l = 1, r = 2가 된다.
3. l = 1, r = 2일 때, people[1] + people[2] ≤ limit을 만족하지 않는다. 따라서 60kg인 사람을 위한 보트를 하나 추가하고 다음 비교를 위해 r을 1 감소시킨다. 즉, answer = 2, l = 1, r = 1이 된다.
4. l = 1, r = 1일 때 두 포인터 모두 50kg인 한 사람을 가리킨다. 따라서 한 사람의 보트가 추가적으로 필요하므로 answer += 1을 하고 r -= 1을 수행한다.
5. l = 1, r = 0일 때, while문을 수행할 조건을 만족하지 않는다. 즉 모든 비교가 종료된다.

 

😎 내 코드

def solution(people, limit):
    answer = 0
    
    people.sort()
    l = 0
    r = len(people)-1
    
    while(l <= r):       
        if l < r and people[l] + people[r] <= limit:
            answer += 1
            l += 1
            r -= 1
        else:
            answer += 1
            r -= 1  
        
    return answer