프로그래머스 - 구명보트 Python

프로그래머스 - 큰 수 만들기

문제유형 : 그리디 알고리즘, 파이썬

해결방법

시간 효율이 계속 실패했던 문제다. 해결방법에 대해서 고민이 많이 필요했다.

• 내림차순으로 정렬한다.
• 리스트 맨 앞과 리스트 맨 뒤 값의 합이 limit 보다 작거나 같다면 같이 구명 보트에 태운다.
• 리스트 맨 앞과 리스트 맨 뒤 값의 합이 limit 보다 크다면 리스트 맨 앞만 구명 보트에 태운다.
• 태울 인원이 limit의 반값보다 작거나 같다면 앞으로는 무조건 두명씩 태울 수 있다.(이 부분을 생각해내야 시간 효율 부분에서 정답 판정을 받을 수 있다.)

def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    i = 0
    j = len(people) - 1
    while i <= j:
        if people[i] <= (limit // 2):
            if (j - i + 1) % 2 == 0:
                answer += ((j - i + 1) // 2)
                break
            else:
                answer += (((j - i + 1) // 2) + 1)
                break
        else:
            if people[i] + people[j] <= limit:
                answer += 1
                i += 1
                j -= 1
            else:
                answer += 1
                i += 1
    return answer