주식가격 문제 바로가기

이중 for문을 이용한 풀이

def solution(prices):
    updown = [0] * len(prices)
    for i in range(len(prices)):
        for j in range(i+1,len(prices)):
            updown[i] += 1
            if prices[i] > prices[j]:
                break
    return updown

queue을 이용한 풀이

def solution(prices):
    updown = []
    for i in range(len(prices)):
        from collections import deque
        current = prices[i]
        check = deque(prices[i:])
        count = 0
        while check:
            temp = check.popleft()
            count += 1
            if current > temp:
                break
        updown.append(count-1)
    return updown

다른 사람들의 풀이 구경하기

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    for i in range(len(prices)):
        while stack != [] and stack[-1][1] > prices[i]:
            past, _ = stack.pop()
            answer[past] = i - past
        stack.append([i, prices[i]])
    for i, s in stack:
        answer[i] = len(prices) - 1 - i
    return answer

출처

CODE REVIEW

  1. 이중 for문 풀이가 간편하지만, 실상 데이터가 늘어나면 늘어날수록 시간이 많이 소요된다. 시간복잡도:O(N^2)
  2. queue을 이용한 풀이도 시도했는데, queue를 활용했다는 점만 다르지 실상 시간복잡도가 O(N^2)라서 시간초과로 효율성에서 꽝이었다.
  3. 다른 사람들의 풀이도 구경해봤는데, 조건문을 이용해서 구하고 count을 1씩 늘려나가는 대신, 범위로 한번에 구해서 효율성을 개선시켰다는 점을 깨달았다. 굳이 필요하지 않은 정보는 메모리절약을 위해 저장하지 말자!