[프로그래머스]구명보트
프로그래머스
구명보트
링크 : 문제 바로가기
1번째 오답
def solution(people, limit):
answer = 0
result = [0]
people.sort(reverse=True)
for person in people:
for i in range(len(result)):
if result[i]+person<=limit:
result[i]+=person
break
elif i==len(result)-1:
result.append(person)
else:
pass
# print(result)
answer=len(result)
return answer
사람들을 몸무게를 기준으로 내림차순 정렬한 후, result리스트에 limit을 고려하며 몸무게가 많이 나가는 인원부터 차례로 넣고, 100이 될때까지 최대한 구명보트에 인원을 계속해서 넣고 안되면 다음 구명보트를 이용하는 방식을 이용했다. 하지만 오답이 생겼다
두번째 오답
문제를 잘못 해석했다. 문제에는 하나의 구명보트에 최대 2명이 탈 수 있다고 했지만, 내 코드는 구명보트에 3명, 4명,… 여러명이 limit만 안 넘는다면 될 수 있는대로 타도록 설정했다. 이 부분을 수정했다.
import math
def solution(people, limit):
answer = 0
result = [0]
people.sort(reverse=True)
# print(people)
while len(people)>=2 and people[0]>(limit/2):
if people[0]+people[-1]<=limit:
del people[0]
del people[-1]
answer+=1
else:
del people[0]
answer+=1
# print(people)
# print(people)
answer+=math.ceil(len(people)/2)
return answer
이때 테스트케이스는 모두 정답 처리되었지만, 효율성 테스트를 통과하지 못했다. 너무 많은 연산시간을 소비하는 듯하다. 나는 리스트를 줄여나가면 효울성에 도움이 될 것이라 생각해 del함수를 사용해 리스트를 줄여나갔다. 리스트에서 인덱스를 이용한 조회가 빅오표기법으로 O(1)의 시간복잡도를 나타내는 것과 같이 del함수도 특정 인덱스를 조회해 삭제하는 것이니 같은 시간복잡도를 가질 줄 알았다. 하지만 del함수의 시간복잡도는 빅오표기법으로 O(N)의 시간복잡도로 리스트의 길이에 비례했다.
해결
import math
def solution(people, limit):
answer = 0
result = [0]
people.sort(reverse=True)
start=0
end=len(people)-1
# print(people)
while people[start]>(limit/2) and start<end:
if people[start]+people[end]<=limit:
start+=1
end-=1
answer+=1
else:
start+=1
answer+=1
answer+=math.ceil((end-start+1)/2)
return answer
두번째 시도에서는 인덱스를 0, -1로 고정하고 리스트 요소를 삭제하는 식으로 설정했는데, 이번에는 리스트는 건들이지 않고 인덱스를 +1, -1시키며 이동하게 설정했다. 이 경우에는 효율성 테스트를 통과했다.
알고리즘 : 탐욕법(greedy)