[알고리즘 고득점 kit/스택, 큐] 주식가격

def solution(prices):
    answer = []
    
    n = len(prices)
    for i in range(n):
        j = i
        while j < n -1:
            j += 1
            if prices[j] < prices[i]:
                break
        answer.append(j-i)
    return answer

 

 

입출력 예시에서 3초 지점 같은 경우, 3초 지점의 3은 바로 뒤에 2가 됐음에도 불구하고 1초간 가격이 떨어지지 않은걸로 본다. 따라서 배열크기만 안넘으면 무조건 j+=1해주고 다시 반복 돌릴지 break로 탈출할지 결정하면 된다.

---

시간 제한이 없었기에 위와 같은 이중 포문 시간복잡도 O(N제곱)의 ㅆㄹㄱ 코드로도 통과는 했지만, 만약 시간제한이 있었다 생각하고 풀어보자.

from collections import deque

def solution(prices):
    answer = [0 for i in range(len(prices))]
    stack = []
    n = len(prices)
    
    for i in range(n):
        if not stack:
            stack.append(i) # 인덱스를 넣어줘야 나중에 answer배열의 인덱스로 접근할 수 있음
        else:
            while stack and prices[stack[-1]] > prices[i]:
                answer[stack[-1]] = i - stack[-1]
                stack.pop()
            else:
                stack.append(i)
    size = len(prices)-1
    while stack:
        answer[stack[-1]] = size - stack[-1]
        stack.pop()
    
    return answer

 

배워가야할...

1. answer배열의 인덱스에 접근해서 넣어줘야 하기에 스택에 값 넣는게 아니라 인덱스 넣어주는거

2. 스택에 남아있는 값들 따로 처리하는거

3. 빈 배열 인덱스로 접근 못하기에 일단 answer배열 0으로 채워넣고 접근해야 하는 것

4. 그리고 제발 인덱스 오버하지말기, pop한 뒤엔 배열 비었는지 체크하고 접근하기