[프로그래머스 - lv2] 주식가격 : slice vs range 효율성 차이 ( Python )

 

코딩 테스트 문제나 풀어볼까?

 

알고리즘 풀기 귀찮은데 친구와 풀기로 약속했기 때문에 제일 쉬워보이는 문제로 꾸역꾸역 풀었다...

매번 느끼는 거지만 쉬워 보이는 것들 막상 해보면 하나도 안 쉽다.

 

 

효율성 문제에 봉착

10분컷이라며 신나서 풀었는데 효율성 보며 오열...

 

이중 반복문을 쓰지 말라는건가??????

근데 아무리 생각해도 이중 반복문 말고는 생각이 안났다.

어쩌라는 거지?

 

........

 

 

문제... 해결?

def solution(prices):
    answer = []
    count = 0
    len_prices = len(prices)
    for i, n in enumerate(prices):
        for j in range(i + 1, len_prices):
            count += 1
            if n > prices[j]:
                break

        answer.append(count)
        count = 0

    return answer

위와 같이 그냥 range로 돌려서 index로 접근해서 비교연산하여 풀면 효율성까지 통과할 수 있다.

 

 

slice와 range의 차이?

 

생각해보니 내가 이전 코드에서는 slice를 쓰고 있었다.

매 번 새로운 리스트를 만드느라 힘들었나봐! 미안해 컴퓨터야

 

라는 생각에

slice는 시간 복잡도가 어떻게 되는지 궁금해서 찾아봤다.

Slice

l[a:b]

O(b-a)

l[:] : O(len(l)-0) = O(N)

( 출처 : 파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) )

 

어라...

생각해보니 range도 정수 배열을 새로 만드는 것 아닌가?

분명 이론상 같은 복잡도를 가질텐데 왜 효율성 측면에서 차이가 나는거지?

 

range의 정체는 C?

C라니 이게 무슨 소리요 난 python으로 짰는데..!

궁금해서 동료에게 물어보고 구글링을 해봤더니 스택오버플로우에 range가 while보다 빠른 이유에 대해 알려주는 글이 나왔다.

range는 최적화를 위해 C코드로 작성되었고, disassembly로 살펴보면 ASM을 잘 모르더라도 연산 횟수가 눈에 띄게 차이나는 게 보인다. 코딩 테스트 문제 쉬운거나 풀어보려다가 갑자기 range의 정체에 대해 알게 되었다. slice가 특별히 느린 게 아니라 range가 최적화를 통해 빨라진거다. 앞으로 반복문을 돌릴 땐 효율성 좋은 range를 써야겠다!

 

더 좋은 방법이 있다면 댓글로 이야기를 나눠도 좋을 것 같다.