코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
- 상세 설명 - 수원대학교(대학일자리 플러스센터)
LV.2 구명보트
앞서 공부한 그리디 알고리즘을 사용해 구명보트 문제를 풀어보겠다.
문제 설명
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
입출력 예
| people | limit | return |
|---|---|---|
| [70, 50, 80, 50] | 100 | 3 |
| [70, 80, 50] | 100 | 3 |
코드
def solution(people, limit):
# 두 명밖에 탈 수 없으니 가장 무거운 한 명, 가장 가벼운 한 명 태워야함
# 무조건 limit은 한 명 태울 수 있는 무게니까 만약 두 명 못 태운다고 하면 한 명만 태우면 됨
# 왜냐 ? 가장 가벼운 한 명을 못태우면 다른 누구도 더 태울 수 없기 때문에
answer = 0
start = 0
end = len(people) - 1
people.sort()
while start <= end:
people_sum = people[start] + people[end]
if people_sum <= limit:
# 한 번에 두 명 옮김
answer += 1
# 따라서 두 명 제외
start += 1
end -= 1
else:
# 한 명만 옮김
answer += 1
# 따라서 한 명 제외
end -= 1
return answer
풀이
먼저 최적의 답을 찾는 방법(그리디 알고리즘)을 생각해본다.
내가 생각한 방법은 아래와 같다.
- 구명 보트엔 두 명밖에 탈 수 없으니 최대한 두 명이 탈 수 있을 확률을 높여 개수를 구한다.
- 따라서 가장 무거운 무게 한 명, 가장 가벼운 무게 한 명을 태우면 된다.
- 만약 가장 무거운 무게 한 명을 태운 상태에서 가장 가벼운 무게 한 명을 못 태우는 경우엔 1명만 가는 걸로 정한다.
- 왜냐 가장 무거운 무게를 한 명 태운 상태에서 가장 가벼운 무게를 못 태운다는 건 그 누구도 같이 탈 수 없음을 의미하기 때문이다.
위의 방법으로 투 포인터를 사용해 코드를 작성했다.
1. 먼저 start와 end의 인덱스를 정하고 탐색하기 위해 people 리스트를 sort()
2. if people_sum <= limit을 만족하는 경우엔 가장 무거운 한 명과 가장 가벼운 한 명을 옮기고 answer += 1
3. 만족하지 못하는 경우엔 가장 무거운 한 명만 옮기고 answer += 1
4. 그렇게 start와 end의 포인터가 만나면 모두 태운 것이므로 return answer
