💡 문제 해결 아이디어

🛠 피드백

• pop(0)은 단순히 제거하는 것이 아니라 지우고 한칸씩 앞으로 당기기 때문에 시간 복잡도가 O(n)이 된다.
• 때문에, collections의 deque를 사용하여 popleft를 하면 해결된다. 혹은 index의 값을 변경하면서 조회하고 answer 값을 변경해주면 될 듯 하다.
  

✨ index의 값을 변경하면서 조회하는 아이디어

1. 오름차순 정렬을 한다.
2. 사용된 구명보트 개수, cnt =0
3. 왼쪽index(left) = 0, 오른쪽index(right) = len(people) - 1

• 여기서 left는 남은 사람 중 가장 가벼운 사람의 index, right는 가장 무거운 사람의 index

4. left가 right보다 같거나 작은 동안 (while)
   • 만약 right의 사람이 limit/2 이하이면 이제부터 무조건 두명씩 탈 수 있기에,
     • cnt += (남은 사람 수 / 2)의 올림
     • break
   • 만약 left사람과 right사람의 합이 limit 이하라면, left사람이 탔으니까
     - left += 1
   • 무조건 right사람은 탔기 때문에 right -= 1
   • 그리고 구명보트를 하나 사용했기 때문에 cnt += 1
   • 마지막에, 만약, 왼쪽index와 오른쪽index가 같으면 같은사람이 한 보트에 2명 타는 것으로 처리되는 셈이지만, 사용된 구명보트는 결국 1개 증가로 동일하기 때문에 문제가 되지 않는다.

내가 생각한 아이디어

1. 오름차순 정렬을 한다.
2. 사용된 구명보트 개수 = 0
3. 사람이 남아있는 동안(while) - 맨 뒤의 숫자(가장 큰 숫자)가 정원제한의 절반 이하인가?

   1. 절반 이하인 경우 : (남은인원/2)의 올림이 필요한 구명보트 갯수이다. (break)

   2. 절반 초과인 경우 : 본인을 제외한 맨 앞의 숫자(가장 작은 숫자)와의 합계가 제한 이하인가?

      1. 합계가 제한 이하인 경우 : 둘 다 리스트에서 제거한다.
      2. 합계가 제한 초과일 경우 : 맨 뒤의 숫자만 리스트에서 제거한다.
      • 결과와 무관하게 구명보트는 1개 사용된다.

💻 작성된 코드

import numpy as np
def solution(people, limit):
	# 오름차순 정렬
    people.sort()
    
    # 사용된 구명보트 개수 
    cnt = 0
    
    # index 지정
    left = 0
    right = len(people) -1
    
    while left <= right:
    	# 가장 무거운 사람이 제한의 절반 이하면, 이제부터 다 두명씩 탈 수 있다.
        if people[right] <= limit/2:
            cnt += np.ceil((right - left + 1)/2)
            break
        # 가장 무거운 사람과 가장 가벼운 사람이 같이 탈 수 있으면
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        cnt += 1
        
    return cnt