https://programmers.co.kr/learn/courses/30/lessons/42885
보트의 제한 무게 - 내 몸무게
가 최소가 되는 사람을 고른다.[]
이 될 때 까지) 반복한다그리디 알고리즘 문제이기 때문에, 최선의 선택을 한다는 것을 보트의 무게를 꽉꽉채워서 보내는 것이라고 이해했었다. 하지만 이런식으로 코드를 작성한다면 가 되어 효율성 테스트를 통과하지 못했다. (물론 정확성조차 맞지 못했지만)
이러면 이기 때문에 효율성은 문제가 없다고 생각했다. 하지만 이렇게 할 경우에,,, 가벼운 사람 두명이 보트를 타는 경우에 대해 고려하지 않는다는 문제가 있었다.
생각해보면, 가장 무거운 사람과 같이 탈 수 있는 사람중 가장 가벼운 사람은, 리스트 내의 그 누구와도 같이 탈수 있게 된다. (어차피 보트의 정원은 2명이기 때문)
그래서 중간에서 끝으로 탐색하지 말고 끝에서 중간으로 탐색하는 것이 가벼운 사람 두명이 보트를 타는 경우에 대해서도 고려할 수가 있다.
def solution(people, limit):
people.sort()
answer = 0
right = len(people) - 1
left = 0
while left < right:
if people[left]+people[right] <= limit:
left +=1
right -= 1
answer += 1
if left == right:
answer += 1
return answer