[프로그래머스 / lv.2] 주식가격

날짜: 2021년 5월 27일
소요 시간: 22분 04초
카테고리: 스택/큐
태그: 레벨2, 파이썬

입출력 예시

prices	return
[1,2,3,2,3]	[4,3,1,1,0]

내가 적은 코드

def solution(prices):
    answer = []
    for i in range(0,len(prices)):
        j = 0
        while prices[i] <= prices[i + j] and i + j != len(prices) - 1:
            j += 1
        answer.append(j)
    return answer

풀이 과정

prices[i+j](비교 주식 가격)이 prices[i](현재 주식 가격)보다 작아질 때까지 j가 1씩 증가하게 하여
비교 주식 가격이 현재 주식 가격보다 작아지면 j를 answer 리스트 원소로 추가한다.

베스트 코드

def solution(p):
    ans = [0] * len(p)
    stack = [0]
    for i in range(1, len(p)):
        if p[i] < p[stack[-1]]:
            for j in stack[::-1]:
                if p[i] < p[j]:
                    ans[j] = i-j
                    stack.remove(j)
                else:
                    break
        stack.append(i)
    for i in range(0, len(stack)-1):
        ans[stack[i]] = len(p) - stack[i] - 1
    return ans

반성

이제 브루트포스 코드보다 자료구조를 생각하면서 시간복잡도를 줄이는 코딩을 신경써야겠다.