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

시간 초과 답안. 비효율적으로 비교가 일어남

대략 생각해보면 복잡도 O(N^2)

효율성 테스트 1, 2, 3, 4를 모두 통과하지 못했다.

def solution(prices):
    answer = [[0, False] for _ in prices]
    # q = deque(answer)
    # print(q)
    # print(q)
    for i, p in enumerate(prices):
        for j in range(i):
            if answer[j][1] == False:
                answer[j][0] +=1
                if prices[j] > p:
                    answer[j][1] = True

    answer = list(zip(*answer))[0]
    return answer

이후 문제 분류처럼 스택이나 큐로 풀어봐야겠다 생각하고 고쳐보았다.

deque의 경우 좌, 우 어디서든 pop해도 시간 복잡도가 O(1)로 알고 있었기에 deque를 활용. 그냥 리스트를 stack으로 생각하고 풀었을 경우에 시간 복잡도 때문에 효율성 테스트를 통과하지 못했다.

from collections import deque
def solution(prices):
    # prev: 이미 비교한 인덱스 저장할 큐
    prev = deque()
    # 각 인덱스 별로 누적해나갈 리스트
    answer = [0 for _ in range(len(prices))]

    # 비교할 후보군들 (지나간 날짜들)
    s = deque()
    # 모든 날짜를 순서대로 탐색
    for i, p in enumerate(prices):
        # s 큐의 경우 비교의 대상이 되는 날짜들
        while s:
            idx = s.popleft()
            # 날짜가 같지 않고, 예전 가격 이상일 경우 우리가 원하는 조건 만족
            if idx != i and prices[idx] <= p:
                prev.append(idx)
            answer[idx] += 1

        # 아직 가격이 떨어지지 않은 날들을 s 에 저장하고, 비어있는 s를 prev로 swap  
        s, prev = prev, s

        # 오늘의 인덱스를 비교 후보군에 저장.
        s.append(i)

    return answer

효율성 테스트 3의 경우 실행마다 통과 여부가 달라짐(통과하는 경우 258ms)