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

문제 링크

i초에 있는 주식 가격이 1이었다면 뒤에 1보다 떨어지는 값이 나올 때까지 몇 초가 걸리느냐의 문제. 문제 설명만 보고 처음엔 그냥 1보다 적은 숫자의 개수를 세라는 건줄 알았는데 도저히 안 풀려서 결국 풀이 코드를 보고나서 문제를 이해했다.. 이런 건 수정안해주나? ㅠㅠ

풀이

현재 위치의 주가가 앞으로 몇 초 동안 유지될 수 있는지를 묻는 문제. 같거나 높다면 유지되는 것이고 1이라도 떨어진다면 떨어지는 것이다. 만약 1이라도 떨어진다면 그 이후는 비교할 필요가 없다.

✔️ 이중 for문 풀이

시간초과 날 줄 알았는데 한 번이라도 감소하면 도중에 break 걸려서 그런가 시간초과가 걸리지 않았다. 단 아래의 스택풀이보다 시간이 더 오래 걸렸다.

def solution(prices):
    answer = []

    for i in range(len(prices)-1):
        x = prices[i]
        sec = 0
        for j in range(i, len(prices)-1):
            if x <= prices[j]:
                sec += 1
            else:
                break
        answer.append(sec)
    answer.append(0)
    return answer

✔️ 스택 풀이

def solution(prices):
    L = len(prices)
    answer = [0] * L
    
    stack = []
    for i, x in enumerate(prices):
        while stack and stack[-1][1] > x:
            idx = stack.pop()[0]
            answer[idx] = i-idx
        stack.append((i, x))
        
    while stack:
        idx = stack.pop()[0]
        answer[idx] = L-1-idx
        
    return answer