[프로그래머스] 주식가격 (python)

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

코딩테스트 연습 - 주식가격

첫 풀이

from collections import deque
import copy

def solution(prices):    
    answer = []
    q = deque(prices)
    
    count = 0
    while q:
        num = q.popleft()
        rest_q = copy.deepcopy(q)
        
        while rest_q:
            count += 1
            if num > rest_q.popleft():
                break
            
        answer.append(count)
        count=0
            
    return answer

이거 머냐구.. 효율성에서 탈락. 내가 봐도 너무 비효율이당.

 

2번째 풀이

from collections import deque
import copy

def find_index(num, q):
    for i, _ in enumerate(q):
        if _ < num:
            return i+1
    return len(q)
        

def solution(prices):    
    answer = []
    q = deque()
    for _ in prices:
        q.append(_)
    
    while q:
        num = q.popleft()
        answer.append(find_index(num, q))
            
    return answer

deepcopy 빼고 구현해서 해결 !

 

 

다른 사람들 풀이 봤는데 시간 복잡도가 마찬가지로 다 O(n^2). 

O(n) 풀이가 있나 싶었는데.. 아시는 분은 댓글 남겨주세요