문제링크: 구명보트
✍🏻 Information
| content | |
|---|---|
| 언어 | python |
| 난이도 | ⭐️⭐️⭐️ |
| 풀이시간 | 79분 |
| 제출횟수 | ∞ |
| 인터넷검색유무 | yes |
🍒 My Code
def solution(people, limit):
answer = 0
people.sort()
l,r = 0,len(people)-1
while l<=r:
if people[l]+people[r]<=limit:
l+=1
r-=1
else:
r-=1
answer+=1
return answer
💡 What I learned
- 이 문제에서 잘못했던것: 최대 2명까지 태울 수 있다는 단서를 놓쳐서 1시간동안 삽질만..^^..
- 이전 코드들
#코드1
while len(people)!=0:
if len(people)==1:
people.pop(0)
elif people[0]+people[-1]<=limit:
people.pop(0)
people.pop(-1)
else:
people.pop(-1) #이걸 0에서 -1로 바꿔주니 효율성1번빼고 통과
answer+=1
return answer
#코드2 - 두명태우는지 몰랐음
answer = 0
people.sort(reverse=True)
start,end = 0, len(people)
while 1:
if sum(people[start:end])<=limit:
start,end = end,len(people)
answer+=1
else:
end-=1
if start==len(people):
break
return answerㄴ 코드1은 효율성테스트를 통과하지 못했는데 pop의 시간복잡도가 o(n)이라고 알고 있었는데 pop(0)과 pop(-1)의 시간복잡도가 다른건지 정렬을 내림차순->오름차순으로 바꿔주고 pop(0)->pop(-1)로 바꿔주니 1번빼고 다 통과했다.
-
pop(0) 의 경우 데이터를 지우고 한칸씩 앞으로 당기기 때문에 O(1)이 아니라 O(n)이된다.
<해결방법>
1) people을 collections.deque()로 만들어 popleft()를 사용
2) pop대신 따로 people_num을 people수로 저장해두고 두명빼면 -2, 한명빼면 -1을 해서 people_num>0일때까지 while문 돌리기 -
greedy algorithm: 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 매순간 가장 좋아 보이는것을 선택하며 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.
ex) 동전문제 - 10 50 100 500처럼 큰 단위의 화폐가 가장 작은 단위의 배수형태일경우 greedy ok. but 100 400 500일 경우에는 불가.
가장 무거운 사람을 태우되 남은 1자리를 가장 가벼운 사람을 태울 수 있는지 확인한다. 남은 사람들 중 가장 가벼운데 무게가 초과됬다는 말은 두번째로 가벼운 사람 역시 초과될 것이라는 뜻이므로 더 이상 고려할 필요가 없게 된다. 초과되면 무거운 사람만 보트에 한명 태우고 나머지 형식도 반복해서 가장 무거운+가벼운 사람의 조합을 사용해 보트를 최소화 한다.
-> but 이렇게 하면 이후의 상황을 생각하지 않고 태우는것이다. 가장 가벼운 사람을 태울 수 있다고하더라도 그 다음 가벼운 사람도 태울 수 있다면 그 사람을 태우는것이 이후의 상황을 생각할경우 더 합리적이기 때문이다.
-> greedy를 언제 사용해야할지 아직 감을 잡지 못했는데 hint로 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 문제에서 제시해준다고 한다.
