[코테] 그리디(Greedy) - 구명보트[프로그래머스]

문제

출처: 프로그래머스 - 구명보트

풀이

주어진 people에서 1명 혹은 2명으로 묶어서 그 길이를 구할 수도 있지만,
간단히 구명보트에 1명씩 태우는 경우를 default로 잡고 2명이 탈 수 있다면 전체 길이 default 값에서 -1씩 차감하여 구하여도 된다.

그리디 문제는 대부분 정렬을 해서 풀이를 진행한다.
왜냐하면 작은 부분에서의 진행 혹은 연산이 전체 부분 혹은 다른 작은 부분에 영향을 주지 않아야 하기 때문이다. 다시 말해 순차적으로 진행을 할 때, 앞 부분의 연산이 뒷 부분의 연산에 논리적은 영향을 주지 않아야 한다.
문제를 예로 들어서 people을 탐색할 때 무게를 기준으로 limit과 비교하여 연산하여 진행을 한다. people에 들어있는 사람들의 무게를 정렬하면 첫번째 사람이 limit 보다 몸무게가 만약 높다면 정렬을 했기 때문에 뒤의 사람은 더 볼 필요가 없다. 논리적인 연산을 진행할 수 있게 된다.

1. people를 정렬하여 첫번째 사람이 몸무게가 가장 작고 제일 뒤의 사람이 몸무게가 가장 높게 만든다.
2. 첫 번째 사람과 가장 뒤의 사람의 몸무게를 더하여 limit보다 작으면 2명을 태울 수 있기에 default에서 1을 빼줘야 하기에 변수를 지정하여 1을 올려주도록 한다.
3. 첫 번째 사람과 마지막 사람을 먼저 구하는 이유는, 순차적으로 무게를 찾아갈 수 있기 때문이다. 두 사람의 합이 limit보다 크다면 같이 타지 못하므로 첫번째 사람을 고정하고 뒤에서 두번째 사람과 같이 탈 수 있는지 확인한다. 몸무게가 가장 큰 사람이 가장 작은 사람과 탈 수 없다면 가장 큰 몸무게를 가진 사람은 혼자 타야 하기 때문이다.
4. 만약 두 사람의 몸무게가 limit보다 작거나 같다면 2명이 탈 수 있기에 그 다음순서로 앞에서 몸무게가 무거운 사람과 뒤에서 몸무게가 가벼운 사람을 다시 탐색하여 연산을 하다.
5. 투 포인터 알고리즘을 활용하며, 3번과 4번의 연산이 문제없이 진행되기 위해서 people를 정렬하는 것이다.

코드

def solution(people, limit):
    n = len(people) # 전체 길이 default 값
    answer = 0 # 2명이 탄 횟수
    s = 0 # 시작 인덱스
    e = len(people) - 1 # 마지막 인덱스
    people.sort() # 정렬
    
    while s < e: # 점점 중앙으로 인덱스가 좁혀오는 형상
        if people[s] + people[e] <= limit:
            answer += 1
            s += 1
            e -= 1
        else:
            e -= 1
            
    return n - answer