[Programmers] 주식가격

[Programmers] 주식가격

 

🎈문제

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

💬설명

• for문을 두번 돌면 되는 문제
• 처음부터 끝까지 돌면서 각각에 대해 뒤에 있는 price들을 체크해준다.
• 데이터 크기도 그렇게 크지 않고 O(nlogn)에 풀수 있어서 효율성도 통과했다.
• 스택으로 풀면 시간이 더 단축된다. (두번째 풀이) (약 100ms -> 약 20ms)

👩‍💻코드

def solution(prices):
    answer = []
    
    for index, price in enumerate(prices):
        answer.append(0)
        for i in range(index + 1, len(prices)):
            answer[-1] += 1
            if prices[i] < price:
                break
    return answer

# stack으로 푼 경우


def solution(prices):
    length = len(prices)
    stack = [0]  # 초기값 넣어주기 index 0
    
    # 감소하지 않을 때 들어갈 수 있는 최대값으로 초기화
    answer = [i for i in range(length - 1, -1, -1)]
    
    # 1번째 값부터 끝까지 돌기
    for i in range(1, length):
        # stack의 top 값을(참고: 스택에 들어있는 값들은 증가하는 수열임)을 체크해서
        # 감소하는 시점을 확인하고 만약 감소한다면 시간 간격을 계산해서 넣는다.
        # 감소하지 않는다면 다음값 확인
        while stack and prices[stack[-1]] > prices[i]:
            top = stack.pop()
            answer[top] = i - top
        stack.append(i)
    
    return answer