[프로그래머스] Lv.2 구명보트

Python3, 그리디 알고리즘

문제

제한 사항

입출력 예시

나의 풀이 (시도)

• 스택에 people이 들어오면 저장
• 스택 데이터를 더한 값이 limit보다 크면 pop
• k ++
• 스택에 있는 값을 다 더해서 limit과 비교하는 부분을 못함

def solution(people, limit):
    answer = []
    k = 0
    
    for i in range(len(people)):
        # 만약 사람이 들어 왔는데 limit가 남으면
        if limit - answer > 0:
            # 스택에 그 값을 저장하고
            answer.append(people[i])
            
        answer.pop()
        k += 1
            
    return k

주요 포인트

투 포인트로 접근하기

start와 end 인덱스 값을 서로 더해서 limit보다 작으면 두 명 이상 보트 탈 수 있음
→ 보트 하나 추가, 다음 start 값으로 이동(start++)
(이걸 위해서 people 배열을 먼저 sort 할 것)

두 명 이상 탈 수 있는 보트가 몇 개인지 계산하고 사람 수에서 그만큼 빼주면 된다

최종 코드

def solution(people, limit):
    answer = 0
    
    start = 0
    end = len(people) - 1
    
    # 배열 작은 순서대로 정렬
    people.sort()
    
    # 인덱스 start, end 투포인트로 접근
    # 두 명 이상 탈 수 있는 보트를 계산하고 사람 수에서 그만큼 빼주기
    while start < end:
        # 만약 사람이 들어 왔는데 limit가 남으면
        if people[start] + people[end] <= limit:
            # 다음 start 값으로 이동
            start += 1
            # 보트 추가
            answer += 1
        end -= 1
            
    return len(people) - answer