[프로그래머스]구명보트(Python)

0. 문제 링크

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

프로그래머스

 

1. 문제 설명

1) 주어진 people 리스트에서 limit 만큼의 최대 두 사람 고르기

2) 필요한 구명보트 반환

 

2. 입출력

# input
people = [70, 50, 80, 50]
limit = 100

# output
return = 3

 

3. 코드

def solution(people, limit):
    answer = 0
    front = 0                                           # 리스트의 처음부터 시작
    rear = len(people)-1                                # 리스트의 끝부터 시작

    people.sort()                                       # 정렬

    while front <= rear:
        answer += 1                                     # 보트 1개 추가
        if people[front] + people[rear] <= limit:       # 몸무게가 가장 적은 사람과 가장 많은 사람이 탑승
            front += 1                                  # front 1 증가
        rear -= 1                                       # rear 1 감소
    
    return answer

 

실행 결과

 

4. 회고

이 문제는 탐욕법(Greedy)에 해당하는 문제로, 탐욕법은 현재 상황에서 가장 좋은 것을 고르는 알고리즘이다. 이 문제를 풀 때는 핵심이 두 가지가 있는데, 첫 번째로는 '정렬'이고, 두 번째로는 '데크(deque)의 front, rear'를 이용하는 것이다. 먼저 정렬을 하는 이유는 몸무게가 적게 나가는 사람과 많이 나가는 사람을 짝으로 구명보트에 타야 하기 때문이다. 데크의 front, rear로 현재 상황에서 몸무게가 가장 적은 사람, 몸무게가 가장 많은 사람의 조합을 찾기 위해서 front, rear를 사용한다. 

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Programmers/life_boat.py

GitHub - iihye/Algorithm