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

 

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

프로그래머스

 

문제를 이해하는 데에 있어서는 어렵지 않았다. 사람들의 몸무게를 합쳐 limit보다 낮게 만들 때 구명보트 하나가 소요된다. 둘이 합쳤을 때 limit보다 크다면 하나씩 구명보트를 이용해야 한다. 그래서 소요되는 구명보트의 최솟값을 구하면 된다.

 

먼저 내가 제출한 코드를 보겠다. 코드 실행에서는 통과했지만 제출 후 채점에서 통과하지 못했다. 

def solution(people, limit):
    answer = []
    people.sort()
    while sum(people) > limit:
        answer.append(people.pop())
    return len(answer)+1

 

문제를 보고 먼저 정렬을 해야겠다고 생각했다. 정렬 후 sum()을 통해 limit보다 크다면 pop을 통해 다른 리스트에 추가해 주었다. 근데 이렇게 단순하게 생각하면 안 된다는 것을 알았다. 만약 제일 마른 사람과 제일 뚱뚱한 사람의 몸무게의 합이 limit이하면 이 둘이 구명보트 하나를 탈 수 있으니까 위에처럼 제일 큰 값을 pop()해주면 안 된다.

그리고 구명보트 개수의 최솟값을 만들어야 하기 때문에 가장 작은 사람의 몸무게와 가장 뚱뚱한 사람을 한 구명보트에 태울 때가 최적의 경우이다.

그리고 이를 구현하기 위해서는 투 포인터를 사용해야 한다. 일반적인 반복문을 사용하면 시간 초과가 발생할 수 있는데 투 포인터를 이용하면 메모리와 시간 효율성을 높일 수 있다. 

 

간단하게 투 포인터에 대해서 알아보도록 하자.

위처럼 두 가지 유형의 투 포인터가 있다는 것과 두가지 포인터를 이용해 리스트에서 원하는 값을 찾거나 반복문을 써야 할 때 효율적이라는 점을 기억하자!

 

다시 문제로 돌아와서, 이 문제는 정렬한 리스트에서 앞에서 시작하는 포인터와 끝에서 시작하는 포인터를 이용하여 두 원소의 값의 합과 limit를 비교하여 합이 limit보다 작으면 start + 1을 하여 start와 end가 만날 때까지 계산하면 된다.

 

• 제출 코드

def solution(people, limit):
    answer = 0
    people.sort()
    start,end = 0,len(people)-1
    while start <= end:
        if people[start] + people[end] <= limit:
            start+=1
        end-=1
        answer+=1
    return answer

 

정답률이 높은 lv.2문제를 풀어보았는데 레벨이 높아질수록 더 이상 무작정 구현하여 풀이하는 문제가 아닌 특정 알고리즘을 알아야만 풀 수 있는 문제들이 슬슬 나오는 것 같다. 빨리 이코테를 보면서 자주 출제되는 알고리즘을 인지하고 익숙해진 다음 문제를 보았을 때 어떤 알고리즘을 사용해야 하는지 떠올리는 게 중요할 것 같다!