[Python] 프로그래머스 구명보트

문제

프로그래머스

 

문제 풀이 (투포인터 + 그리디)

• 최대 두 명의 사람을 한 보트에 태워보낼 수 있으므로 가장 가벼운 사람 + 가장 무거운 사람을 한 보트에 태워 보내야한다.
• 가장 가벼운 사람과 무거운 사람의 무게를 합한 값이 limit와 같거나 작으면 두 명을 한 보트에 태워 보낼 수 있는 것이므로 양쪽의 포인터를 옮긴다.
• 합한 값이 limit보다 크다면 한 명만 보트에 태워 보낼 수 있으므로 가장 무거운 사람만 먼저 보낸 후 end 포인터만 옮긴다.
• 각 연산 시 보트에 사람을 태워보냈으므로 answer값도 1씩 증가시킨다.

코드

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

---

오답 코드

def solution(people, limit):
    stack = []
    sum_val = 0
    answer = 0
    people.sort()
    for i in range(len(people)):
        sum_val += people[i]
        if sum_val <= limit:      
            stack.append(people[i])
        else:
            sum_val = people[i]
            while stack:
                stack.pop()
            answer += 1
            stack.append(people[i])
    
    if stack:
        val = stack[0]
        if val <= limit:
            answer += 1
        else:
            if val % 2 == 0:
                answer += (limit // val)
            else:
                answer += (limit // val + 1)
    return answer

최대 두 명의 인원만 보트를 탈 수 있다는 전제가 아닌 전체인원을 전제로 푼 코드라 오답이다.

문제를 잘 읽자 ^^