프로그래머스 #3 그리디 > 구명보트

문제 설명

• 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다.
• 구명보트는 작아서 한 번에 최대 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

---

풀이

• 처음에 문제에 2명씩만 탈 수 있다는 문장을 안 읽어서 온갖 고민을 다 하다가 몇 시간뒤에 다시 읽어보고 소름 돋았던 문제
• -> 문제를 꼼꼼히 잘 읽자

• 2명씩 타는 걸 몰랐을 때 풀이 방식

• 무거운 사람 순서대로 정렬 후 첫 사람과 다음 사람을 비교 후에 limit 과 비교, limit 이상이면 그 다음 사람과 비교...반복

• -> 계속 시간초과

• 시간 초과가 날 수 밖에 없는 코드 였다

• 다시 도전 해서..

• 생각을 바꿔서

• -> 처음 사람들의 숫자만큼 보트가 있다고 가정한 후에 2명이 탈 수 있을 때 보트 수를 1개 감소 시켜보기로 했다

• 2명이 탈 때 : 제일 무거운 사람과 제일 가벼운 사람이 타면 된다

• -> 몸무게 무거운 순서대로 정렬 후

• -> 맨 처음(0번째) 와 맨 마지막(len - 1) 을 합쳐서 limit 과 비교

• -> 같이 타게 되면 : limit 보다 작거나 같을 때

• --> 무거운 사람(1번째) 와 가벼운 사람(len - 2) 가 되어야 하니 각각 p1, p2 를 - 1 시켜준다

---

코드

• def solution(people, limit):
      answer = len(people)
      # 무거운 순서대로
      people.sort(reverse=True)
  
      # 무거운 사람 인덱스
      p1 = 0
  
      # 가벼운 사람 인덱스
      p2 = len(people) - 1
  
      while p1 < p2:
  
          # 몸무게가 제일 큰 사람 + 작은 사람이 같이 탈 경우
          if people[p1] + people[p2] <= limit :
  
              answer -= 1
              p2 -= 1
  
          p1 += 1
  
      return answer