프로그래머스 구명보트

https://programmers.co.kr/learn/courses/30/lessons/42885?language=python3 

코딩테스트 연습 - 구명보트

 

 

첫 시도는 효율성 테스트에서 실패

def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    while people:
        tmp = people.pop()
        for x in people:
            if tmp + x <= limit:
                people.remove(x)
                break
        answer += 1
    return answer

 

1. 리스트를 내림차순으로 정렬

2. people리스트가 빌때까지 리스트 맨뒤에 가벼운 사람과 같이 탈 수 있는 사람이 있는 지 앞에서부터 확인하고 리스트에서 제거

 

 

 

 

개선 코드

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
        answer += 1
    return answer

 

1. 리스트 정렬

2. start와 end 카운터를 생성하고 end가 start보다 작거나 같을때까지 반복

    2-1 start와 end를 더해 limit보다 작으면 start +1, end -1 (같이 보트에 태움)

    2-2 start와 end를 더해 limit보다 크면 end -1 (end 혼자 보트에 태움)