[프로그래머스] 구명보트 문제풀이 python

🐒 문제

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

✍ 나의 풀이

def solution(people, limit):
    answer = 0

    people.sort()
    
    left, right = 0, len(people)-1
    
    while left <= right:
        if left == right:
            answer += 1
            break

        if people[left] + people[right] > limit:
            right -= 1
            answer += 1
        else:
            answer += 1
            left += 1
            right -= 1

    return answer

그리디 문제, 투포인터 이용

---

🧠 문제 이해

최대 2명이 탈 수 있고 무게 제한이 limit인 구명보트을 통해 people의 사람들을 태워야 할때, 필요한 구명보트의 최소 갯수를 리턴.

people = [1, 4, 3, 5]
limit = 7

일때

마구잡이로 앞에서부터 구명보트에 태우면 (1,4) (3) (5) 로 태워야한다.

people 을 정렬하여

[1, 3, 4, 5]

가장 왼쪽과 가장 오른쪽끼리 짝을 지어 태우면 (1,5) (3,4) 로 두개의 구명보트로 태울 수 있다.

def solution(people, limit):
    answer = 0

    people.sort()
    
    left, right = 0, len(people)-1
    
    while left <= right:	# left가 right보다 같거나 작을때까지만 반복
        if left == right:	 # 마지막 구명보트에 무거워서 한명이 못타는 경우
            answer += 1		 # 구명보트 한대 더 가져옴
            break

        if people[left] + people[right] <= limit:	# 현재 가장 작은 값과 가장 큰값을 합한 값이 무게제한보다 같거나 작으면
        	answer += 1	# 둘이 구명보트 한대에 타세요
            left += 1	# 왼쪽 커서 오른쪽으로 한칸이동
            right -= 1	# 오른쪽 커서 왼쪽으로 한칸이동
        else:	# 한명이 무거우면
            right -= 1 # 오른쪽 커서 왼쪽으로 한칸
            answer += 1	# 무거운놈 혼자 구명보트 타세요

    return answer

---

다른풀이

def solution(people, limit) :
    answer = len(people)
    
    people.sort()
	
    left, right = 0, len(people)-1
    
    while left < right :
        if people[left] + people[right] <= limit :
            left += 1
            answer -= 1
        right -= 1
    return answer

위 코드는 맨처음 구명보트 한대에 한명씩 탄다고 가정하고나서,
둘이 짝지어 보트를 타면 한대가 필요 없어지는 아이디어로 구현된 코드이다.