그리디 문제로 리스트로 사람들의 무게가 주어지고 구명보트의 최대 수용무게가 주어진다. 이때 무인도를 탈출할수있는 최적의 구명보트 개수
구명보트의 최솟값을 구하는 문제이다.
여기서 중요한 부분은 한번에 최대 2명씩 탈수있다는 거다
최대 2명이라는 항목이없으면 최솟값을 limit 밑으로 계속추가할수있지만 2명이기 때문에 최적의 사람을 구해야된다. limit이 100이라고 치면
40, 50 , 60 100 50, 이있다고 치면 최솟값부터 넣는 40,50 이 좋은 해결법이 아니라 40, 60넣고 50,50 넣는게 더 좋은 해결법이라는 걸 알고있어야된다 ㅠㅠ
처음에 sort해놓고 최솟값으로 풀었더니 안풀렸다 그리고 시간제한도 빡쌔서 pop이나 이러한 indexing요소들을 사용하면 효율성도 통과를 못했다
def solution(people, limit):
answer = len(people)
new_people = sorted(people, reverse=True)
i = 0
j = len(new_people) - 1
while i< j:
if new_people[i] + new_people[j] <= limit:
j -= 1
answer -= 1
i += 1
return answer
answer는 그냥 사람들의 숫자로 해놓고 2명씩 들어가면 1씩 줄어드는 방식으로 푼다.
사람들의 몸무게를 내림차순으로 정렬 (오름차순으로해도상관없다)
i는 최대값부터 j는 최소값부터
최대 2명만 보트에 탈수 있으니깐 2명씩만 비교해주면된다.
최소값과 최대값을 더해서 limit보다 같거나 같으면 -> index를 하나씩 줄이고 올려주고 2명이타는거기때문에 answer를 1줄여준다.
그러면 정답! 이나온다...
깨달은 점
보통 zero에서부터 문제를 푸는 answer =0 으로 부고 푸는 방법만 생각하였는데 정답을 최악의경우로 두고 2명씩 들어가면 1씩빼는 방법을 생각하지 못했다. 이방법이 이런 효율성 문제에 대해서는 좋은 방법인거 같다.
좀더 말랑말랑한 사고를 해야되겠다.
