[프로그래머스]구명 보트

[83] 구명보트

책 구매하기

문제 정보

• 분류: 그리디
• 정답률: 68%
• 권장 시간 복잡도: O(N log N)
• 핵심 키워드: 투 포인터, 정렬, 구명보트, 가벼운 사람 매칭
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42885

문제를 읽을 때 체크할 포인트

가장 무거운 사람은 어차피 보트 하나를 꼭 차지한다. 여기에 가장 가벼운 사람을 같이 태울 수 있으면 태우고, 안 되면 혼자 보내는 식으로 정리하면 된다.

한 번의 선택 기준이 맞는지만 확인되면 그 뒤는 같은 규칙을 반복하면 된다. 결국 매 순간 무엇을 먼저 선택해야 전체가 가장 이득인지 보는 문제다.

풀이 흐름

1. 사람 몸무게를 정렬한다.
2. 무거운 사람 쪽과 가벼운 사람 쪽에 포인터를 둔다.
3. 둘을 함께 태울 수 있으면 둘 다 이동, 아니면 무거운 사람만 보내며 보트 수를 센다.

구현할 때 놓치기 쉬운 부분

가장 무거운 사람을 기준으로 가장 가벼운 사람과 함께 탈 수 있는지 먼저 봐야 한다. 무거운 사람끼리 먼저 묶거나 앞에서부터 순서대로 넣으면 배 수가 늘어난다.

파이썬 정답 코드

def solution(people, limit):
  # 사람 몸무게를 정렬한다.
  people.sort()
  left, right = 0, len(people) - 1
  answer = 0

  # 무거운 사람 쪽과 가벼운 사람 쪽에 포인터를 둔다.
  while left <= right:
    # 둘을 함께 태울 수 있으면 둘 다 이동, 아니면 무거운 사람만 보내며 보트 수를 센다.
    if people[left] + people[right] <= limit:
      left += 1
    right -= 1
    answer += 1

  return answer

시간 복잡도

N은 people의 길이이다.

핵심 비용은 정렬이다. N개 데이터를 정렬하는 데 O(N log N)이 들고, 정렬 뒤에 붙는 한 번의 순회나 해시 조회는 선형이라 전체 차수를 바꾸지 않는다.

따라서 시간 복잡도는 O(N log N)이다.