[Programmers] Level 2. 구명보트

🔗 Problem Link

Level 2. 구명보트

❔Thinking

• limit을 넘지 못하는 2인승 보트를 최대한 적게 사용하여 모든 사람들을 탈출시킨다.
• 보트를 사용한 횟수를 출력한다.

💻Solution

1. 시간초과 풀이

   def solution(people, limit):
       answer = 0
       people.sort(reverse=True)
       while people:
           flag = False
           left_weight = limit - people[0]
           for i in range(1,len(people)):
               if left_weight >= people[i]:
                   people.remove(people[i])
                   people.pop(0)
                   flag = True
                   answer += 1
                   break
           if flag is False:
               answer += 1
               people.pop(0)
       return answer

2. 성공한 풀이

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

🗝️keypoint

• 몸무게를 오름차순으로 정렬하면, 비효율적인 보트 운행의 경우는 없다.
• 배열에서 값을 제거할 필요 없이, 보트를 운행하는 횟수만 구하면 시간복잡도가 줄어든다.