[Python] 구명 보트

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

프로그래머스

# 시간 초과가 나옴
def solution(people, limit):
    people.sort()
    answer = 0
    
    while len(people)>1:
        if people[-1] + people[0] <= limit:
            people = people[1:-1]
            answer += 1
        else:
            people = people[:-1]
            answer += 1
            
    if len(people)==1:
        answer += 1
        
    return answer

정답은 맞았지만 마지막 효율성 부분에서 시간초과로 탈락함

 

• 다른 사람의 풀이

# 다른 사람 풀이
def solution(people, limit) :
    answer = 0
    people.sort()

    a = 0
    b = len(people) - 1
    while a < b :
        if people[b] + people[a] <= limit :
            a += 1
            answer += 1
        b -= 1
    return len(people) - answer

최소와 최대를 묶어서 같이 보트를 태운다는 아이디어는 동일함.

 

차이점은 인덱스를 이용해서 찾아 나간다는 점이 다름.

 

마지막 리턴값이 len(people) - answer인 이유는 애초에 두 명을 묶어서 보내는 경우의 개수만 측정했기 때문임.

 

모든 사람을 한 명씩 태워보내면 len(people)이고, 두 명을 묶어서 태워보내는 경우를 빼줘야함