[프로그래머스 lv 2] 구명보트 (탐욕법(Greedy))

아이디어 : 작은 순으로 정렬한 후에 2명씩 태워보면 되지 않을까 싶다.

 

# 첫 번째 시도

def solution(people, limit):
    answer = 0

    people.sort()
    people.append(0)
    flag = 0
    
    for i in range(0,len(people)-1,2):
        if people[i]+people[i+1] <= limit:
            answer+=1
        else:
            flag = i
            break
    answer += len(people)-1-flag
    
    return answer

 

그런데 고려하지 못했던 부분은, 작은 순대로 차례로 넣는게 아니라 큰수와 작은 수를 잘 조합하면 limit을 넘기지 않을 수 있다는 것이다. 예를 들면 [10, 20, 30, 40, 50, 60, 70, 80], limit=90 -> return 4와 같은 테스트케이스를 생각해볼 수 있다.

 

# 두 번째 시도

 

• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

def solution(people, limit):
    answer = 0
    flag = 0
    people.sort(reverse=True)

    for i in range(len(people)):
        if people[i]+people[-1]>limit:
            answer+=1
        else:
            flag = i
            break

    people = people[i:]
    people.sort()
    
    if len(people)%2==0:
        answer+=len(people)/2
    else:
        answer+=(len(people)//2)+1
    
    return answer

 

그런데도 안되긴 한다. 어떤 경우를 빠뜨린 걸까? 테스트케이스 여러개를 시도해보았지만 잘 모르겠다.

-> 만약 [10, 30, 30, 30, 40, 40], 40와 return 5로 두면 실패한다. 왜냐하면 현재는 제일 작은 값과 큰 값들과의 합만 고려하고 있기 때문에, 제일 처음 값만 작고 중간값이 큰 경우에는 더할 수가 없기 때문이다.

 

# 세 번째 시도(성공)

def solution(people, limit):
    answer = 0
    flag = 0
    people.sort()

    left=0
    right=len(people)-1
    while left < right:
        if people[left]+people[right]<=limit:
            answer+=1
            left+=1
            right-=1
        else:
            right-=1
    answer += len(people)-answer*2
    return answer