(프로그래머스) 연습문제 - 구명보트

Link

• https://programmers.co.kr/learn/courses/30/lessons/42885

Introduction

그리디 알고리즘 문제는 쌀 가마니에서 어떤 ‘되’를 사용하여 다른 용기로 옮겨 담는 이미지가 떠오른다.

이 광경은 그리디 알고리즘의 두 가지 조건인 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)을 보여준다.

1. 탐욕스런 선택 조건: 앞의 선택이 이후의 선택에 영향을 주지 않는다.
   • 한 되를 퍼서 옮기고 빈 되가 되면 다시 또 한 되를 퍼낼 수 있다.
2. 최적 부분 구조 조건: 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해이다.
   • 한 되, 한 되를 가장 많이 퍼낼 수 있어야 전체적으로 가장 빠르게 원하는 만큼을 옮겨 담을 수 있다.

1번 조건의 경우는 기존의 연산 결과가 현재의 연산 결과에 영향을 미치는 DP와는 완전히 반대되는 느낌이다.

Note

• while 문이 끝나고 체크되지 않은 보트 하나를 잊지 말 것

Solution

def solution(people, limit):
    answer, boat = 0, 0
    left, right = 0, len(people)-1
    people.sort()

    while left <= right:
        if people[right] + boat <= limit:
            boat += people[right]
            right -= 1
        elif people[left] + boat <= limit:
            boat += people[left]
            left += 1
        else:
            answer += 1
            boat = 0
    return answer+1

1. 필요한 변수 정의

투 포인터로 문제를 풀거라 포인터 2개와 사람을 태울 보트가 필요하다.

def solution(people, limit):
    answer, boat = 0, 0
    left, right = 0, len(people)-1

2. Greedy

우선 누가 무겁고 가벼운지를 알기 위해 무인도에 있는 사람들을 몸무게 순으로 일렬로 세운다.

def solution(people, limit):
    answer, boat = 0, 0
    left, right = 0, len(people)-1
    people.sort() # 2-1

어떤 공간에 물건을 배치할 때 보통 큰 물건부터 배치하고 작은 물건은 남은 공간에 테트리스 하듯이 배치한다.

그리고 이 방식은 공간을 효율적으로 사용할 수 있는 방법으로서 많은 사람들이 이미 체화한 방법이다.

이걸 이번 풀이에도 적용해보자. 보트에 더 사람을 태울 수 없을 때는 보트를 보내서 보트를 비워준 후 정답 카운트를 1개씩 올려준다.

def solution(people, limit):
    answer, boat = 0, 0
    left, right = 0, len(people)-1
    people.sort()

    while left <= right: # 2-2
        if people[right] + boat <= limit:
            boat += people[right]
            right -= 1
        elif people[left] + boat <= limit:
            boat += people[left]
            left += 1
        else:
            answer += 1
            boat = 0

while 문이 끝나는 조건은 left나 right가 움직여서 left가 right보다 더 커질 때이다.

즉, else문으로 들어간 뒤 while문을 빠져나가는 경우는 없기 때문에 마지막에 무조건 boat에는 누군가 타 있고 이 사람들은 카운트 되지 않은 상태이다.

따라서, 이 사람들을 마지막으로 카운트 해준다.

def solution(people, limit):
    answer, boat = 0, 0
    left, right = 0, len(people)-1
    people.sort()

    while left <= right:
        if people[right] + boat <= limit:
            boat += people[right]
            right -= 1
        elif people[left] + boat <= limit:
            boat += people[left]
            left += 1
        else:
            answer += 1
            boat = 0
    return answer+1 # 2-3

Comment

그리디 알고리즘에서는 옮겨 담을 쌀과 되가 어떤 것인지를 명확히 하는 것이 중요한 것 같다. 그리고 담을 때 부피가 큰 것 부터 담는다는 것 정도?