프로그래머스 문제풀이
문제
문제설명
무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
입출력 예
| people | limit | return |
|---|---|---|
| [70, 50, 80, 50] | 100 | 3 |
| [70, 80, 50] | 100 | 3 |
입출력 예 설명
없음
문제해석과정
- 이번 문제를 요약하자면 탐욕법을 사용하여 해결하는 문제입니다.
- 정해진 조건과 몸무게를 이용하여 보트의 최소 사용수를 구하는 문제입니다.
- 조건으로는 주어진 인원들의 몸무게, 배의 무게제한, 인원제한이 있습니다.
- 이번문제에서 어려운점은 정답뿐 아니라 효율성도 좋도록 코딩을 해야한다는 것입니다.
문제 풀이전에 지문과 제한사항을 반드시 읽으시길 바랍니다.
나의 풀이
이번 문제에서는 개인적으로 시간이 많이 들었습니다. 효율성테스트때문에 말이죠…
이 문제는 모로가든 도로가든 어떻게든 풀수있습니다. 다만 채점시 효율성도 따지므로 이 부분을 주의해줘야 합니다.
1차코드(실패)
일반적인 리스트와 pop 사용해서 해결했을때, 효율성 1번테스트에서 시간초과가 발생했다.
문제는 people.pop(0) 코드때문이다.
리스트에서 리스트.pop(), 리스트.pop(-1)의 경우 O(n)가 1이 된다.
하지만 리스트.pop(0), 즉, 리스트.pop(i)를 하면 O(n)가 n이 된다고 한다.
def solution(people, limit):
answer = 0
people.sort()
while len(people) > 0:
# 값이 하나일때
if len(people) == 1:
people.pop()
answer += 1
break
# 값이 둘 이상일때
if people[0] + people[-1] > limit:
people.pop()
answer += 1
else:
people.pop(0)
people.pop()
answer += 1
return answer
2차코드(성공)
1차코드 실패 후 deque를 사용하는 코드로 변경해주었다.
deque 사용시 양끝을 pop() 또는 popleft()로 제거해줄 수 있고, 제거시 O(n)은 1이 된다.
효율성테스트 1번 실패로 많은 시간을 소모했지만, 리스트의 시간복잡도에 대해 더 알게되는 계기가 되었습니다.
from collections import deque
def solution(people, limit):
answer = 0
deq = deque(sorted(people))
while len(deq) > 0:
# 값이 하나일때
if len(deq) == 1:
deq.pop()
answer += 1
break
# 값이 둘 이상일때
if deq[0] + deq[-1] > limit:
deq.pop()
answer += 1
else:
deq.popleft()
deq.pop()
answer += 1
return answer
다른 사람의 풀이
아래는 다른 풀이를 가져와봤습니다.
deque를 사용하지않고 리스트에서 짝지은 인원수를 구해서 총 인원에서 빼주어 보트수를 구했네요
창의적이네요. 한 수 배웁니다.
def solution(people, limit) :
answer = 0
people.sort()
a = 0
b = len(people) - 1
while a < b :
if people[b] + people[a] <= limit :
a += 1
answer += 1
b -= 1
return len(people) - answer
관련 링크
문제해결과정에서 기초가 부족하다고 느껴지시면 아래 정리 글을 참고해주세요.
추가적으로 궁금한 사항이나 글에 대한 개선점 알려주시면 피드백 적극 반영하도록 하겠습니다.
