[프로그래머스/Python] 탐욕법(그리디) - 구명보트

• 처음 문제를 보고, pop과 remove만 생각했다. 그게 깔끔하다고 생각해서,,하지만 그건 효율성 부분에서 낮게 나온다고 한다 (찾아보니까,,) 나름 쉬운 문제였는데 내가 고민을 덜 해본건지 뭔지 풀만하다고 생각했는데 이 문제도 1시간을 붙잡고 있는걸 보고,, 참 (절레절레) 결국 구글링의 도움을 받았다.
• 결론: index로 접근해야함

풀이

def solution(people, limit):
    answer = 0
    i = 0
    j = len(people) - 1
    # people = [50, 50, 70, 80]
    people.sort()
    while i <= j:
        answer += 1
        if people[i] + people[j] <= limit:
            i += 1
        j -= 1     
    return answer

• people을 오름차순으로 정렬 (디폴트 정렬)
• 가장 무거운 사람(people[j])과 가장 가벼운 사람(people[i])의 몸무게를 차례대로 더해가며 limit보다 작거나 같으면 같이 보내고, 무거우면 제일 무거운 사람부터 차례대로 보내는 방식
• i가 j보다 작거나 같다면 반복문을 계속 수행 (= j가 i보다 커지면 종료)
  • people[j] + people[i]이 limit 보다 작거나 같다면 같이 보낸다
    • i + 1 하고 j - 1
  • 크다면 무거운 사람부터 보낸다.
    • j - 1

22.06.23 수정

해결 과정

• 먼저 사람들의 무게를 내림차순으로 sort
• 가장 큰 값과 가장 작은 값을 비교한다.
• for문
  • if 다 짝지어서 배타고 가고 한 사람만 남았을 때 break
  • if 짝지었을 때 limit보다 작거나 같을 때
    • 이 때 다 짝지어서 다음 비교할게 없을 때 break

시행착오

• 예제 문제는 맞았는데 왜 틀린거지? -> 예외처리를 잘 해줘야함

def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    flag = len(people) - 1
    for i in people:
        if i + people[flag] > limit:
            answer += 1
        else:
            answer += 1            
            if i == people[flag-1]:
                break
            else:
                flag -= 1
    return answer

• 예외처리
  • [80,70,50,50]일 때 3번째 값과 flag값을 비교 후 더이상 비교할 게 없을 때는 break
  • [80,70,40,30,20]일 때 3번째 값과 비교할 게 없을 때 break

풀이

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