[Programmers_Python] 구명보트

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

프로그래머스

내 풀이

def solution(people, limit):
    people = sorted(people, reverse = True)
    cnt = 0
    while people:
        if len(people) >= 2:
            n = limit - people[0]
            for i in range(1, len(people)):
                if people[i] <= n:
                    people.pop(i)
                    break
            people.pop(0)
        else:
            people.pop(0)
        cnt += 1
        # print(people, cnt)
    return cnt

내 코드로 하니 효율성 테스트에서 전부 시간 초과가 났다... 아마 while문 안에 for문이 하나 더 있어서 발생한 것 같다. 한번 저렇게 풀어야된다라 생각하니 다른 접근 방식이 생각나지 않았다. 그래서 다른 분들의 블로그를 참고 했는데 people리스트를 정렬하는건 맞았으나 그 다음 단계가 달랐다.

 

정답 풀이

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

• answer = 0, start = 0, end = len(people)-1로 초기 설정
• people[start] + people[end] <= limit이면 start += 1, end -= 1
• people[start] + people[end] > limit이면 end -= 1
• 한번 할때마다 answer += 1
• start <= end 동안 while문 반복

이런 방식으로 하면 while문 하나로 문제를 풀 수 있어 시간초과가 나지 않는다!

 

그림 설명!