Py) 프로그래머스 42885 구명보트

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

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

 

내가 짜는 코드는 효율성 테스트를 한 번에 통과하는 경우가 거의 없다-

그래도 정확성 테스트를 통과함에 큰 의의를 둔다.

 

* 최적화 전

딱 봐도 효율성 통과 못하게 생기긴 함ㅇㅇ 너무 막 짰다.

def solution(people, limit):
    answer = 0
    people=sorted(people, reverse=True)

    while len(people):
        comp = len(people) - 1
        while comp >= 0:
            if len(people) == 1:
                del people[0]
                answer += 1
                break
            if people[0]+people[comp] > limit:
                if comp == len(people) - 1:
                    answer += 1
                    del people[0]
                    break
                del people[comp+1]
                del people[0]
                answer += 1
                break
            else:       # 합이 limit와 크거나 같을 때
                del people[comp]
                del people[0]
                answer += 1
                comp -= 1
                break


    return answer

이중 반복문 없앴는데 또 시간 초과 뜸

def solution(people, limit):
    answer = 0
    people=sorted(people, reverse=True)

    comp = len(people) - 1
    while comp >= 0:
        if len(people) == 1:
            del people[0]
            answer += 1
            break
        if people[0]+people[comp] > limit:
            if comp != len(people) - 1:
                del people[comp+1]
        else:       # 합이 limit와 크거나 같을 때
            del people[comp]
            comp -= 1

        del people[0]
        answer+= 1
        comp -= 1

    return answer

뭐가 그렇게 잡아먹는걸까 싶어서 시간 복잡도를 찾아봤다

deque를 쓰면 뭐가 달라질까 싶었는데 deque 양끝 접근 시 O(1), 중간 접근 시 O(n)

del은 양끝, 중간 상관없이 O(n)인듯했고, pop도 생각해봤으나 맨 뒤 접근시에만 O(1)이었다.

list를 deque로 바꿔볼까 싶었다.

 

*최종

from collections import deque
def solution(people, limit):
    deq = deque(sorted(people, reverse=True))
    answer = 0

    comp = len(deq) - 1
    while comp >= 0:
        if len(deq) == 1:
            deq.popleft()       # 인덱스 0 지움
            answer += 1
            break
        if deq[0]+deq[comp] > limit:
            if comp != len(deq) - 1:
                deq.remove(comp+1)

        else:       # 합이 limit와 크거나 같을 때
            deq.pop()
            comp -= 1

        deq.popleft()
        answer+= 1
        comp -= 1

    return answer

사랑해요 deque

사랑해요 시간복잡도 정리해놓으신 분들

이제 이런거 나오면 deque만 쓴다ㅠ

시간 복잡도의 중요성을 느끼게 된 날,,,