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

문제

프로그래머스 코딩테스트 고득점 Kit - 탐욕법(Greedy)

• Lv 2. 구명보트 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/42885

코드 구현

def solution(people, limit):
    answer = 0

    people = sorted(people)     # 정렬해서 (가벼운 사람 + 무거운 사람) 조합으로 최적의 해를 구해야함

    start = 0
    end = len(people) - 1

    while (start <= end):
        # 무게 제한보다 크다면 -> 마지막 인덱스를 가르키는 end 한칸 앞으로 당겨와서 그 다음 무거운 사람으로 비교
        if (people[start] + people[end] > limit):
            answer += 1
            end -= 1

        # 무게 제한을 넘지 않는다면 -> 최대 2명이 타게 됨 (가벼운 사람 + 무거운 사람)
        else:
            answer += 1
            start += 1      # 그 다음 가벼운 사람
            end -= 1        # 그 다음 무거운 사람

    return answer

풀이

• 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고 …
  이 조건을 못봤어서 자꾸 예제만 맞고 정답 테케에서 수두룩 틀렸었다 … (이거 때문에 거의 1시간 걸렸는데… ㅡㅜ)
• 최적의 해를 구하기 위해서는 정렬한 후 → 앞에서부터 가벼운 사람 + 뒤에서부터 무거운 사람 조합으로 보트를 태워야한다.
• start와 end 변수를 사용해서 투포인터로 해결하였다.
  • start는 맨 앞인 0부터, end는 맨 뒤인 len(people) - 1부터 시작한다.
  • start가 end를 넘어가게 되면 모든 사람을 다 태우게 된 것이므로 탈출 (while문의 조건)
  • 두 인덱스에 있는 값을 더해서 limit과 비교한다 !
    • 더한 값이 limit보다 크면 → start에 있는 사람은 못타고 우선 end에 있는 사람만 혼자 보트를 타서 보냄 → end 값만 1 빼준다.
    • 더한 값이 limit보다 작으면 → 최대 2명 탈 수 있는 보트에 [start에 있는 사람 + end에 있는 사람] 이렇게 둘 조합으로 타서 보냄 → end값도 1 빼주고 start는 1 더해주어 다음 비교를 진행한다.