구명보트 (Programmers 42885)

문파이더맨·2021년 7월 3일
0

Algorithm

목록 보기
36/58
post-thumbnail

🧑‍💻 구명보트

  • 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
  • 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
  • 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
  • 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
  • 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
  • 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
  • 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

peoplelimitreturn
[70, 50, 80, 50]1003
[70, 80, 50]1003

🧑‍💻 해결방법

  • deque를 사용하려했으나 실패 후 다른 방법을 도모했다.
  • people을 정렬한 뒤 가장 큰 값을 기준으로 로직을 형성하면 된다.

🧑‍💻 코드

from collections import deque
def solution(people, limit) :
   answer = len(people)
   ppl = sorted(people, reverse=True)

   sp, ep = 0, len(ppl) - 1

   while sp < ep :
       if ppl[sp] + ppl[ep] <= limit :
           ep -= 1
           answer -= 1
       sp += 1

   return answer

def solution_mine(people, limit) :
   answer = 0
   people.sort()
   que = deque(people)

   while que :
       if len(que) >= 2 :
           if que[0] + que[-1] <= limit:
               que.pop()
               que.popleft()
               answer += 1
           elif que[0] + que[-1] > limit:
               que.pop()
               answer += 1
       else :
           if que[0] <= limit :
               que.pop()
               answer += 1

   return answer

🧑‍💻 총평

  • 사고가 굳었다.. 좀 더 유연한 사고가 필요하다.
  • 아직 한~참 멀었다.
  • 좀 더 고심하고 좀 더 생각하자
profile
Sever 개발할래요.

0개의 댓글