[프로그래머스] 주식가격 풀이



1. 문제

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

2. 풀이 방법

  • 2중 for문을 이용하여 뒤에 있는 요소 중, 가격이 줄어드는 요소를 확수 있습니다.
  • Stack(작은 숫자가 아래있고 위로 같거나 큰 숫자가 쌓이는 구조)을 이용하여 문제를 해결할 수 있습니다.
  • 자세한 풀이는 하기에서 계속됩니다.

3. 소스코드

3.1. 2중 for문을 이용한 $ O(n^{2}) $ 방법으로 풀기

def solution(prices):
    answer = [0] * len(prices)

    for i in range(len(prices)-1):
        for j in range(i, len(prices)-1):
            if prices[i] > prices[j]:
                break
            answer[i] +=1
    return answer

3.2. Stack을 이용한 풀이

  • stack에 먼저 0번 index에 해당하는 요소를 집어 넣습니다. 이 stack의 가장 밑에는 가장 작은 수가 들어가있고, 위로 갈수록 숫자가 같거나 커지는 형태를 가집니다.
  • 1부터 p-1 까지 for문을 돌면서 stack 가장 위에 있는 요소와 크기를 비교합니다.
    • 현재 비교하는 배열의 값과 stack의 상단 요소가 같거나 크면, stack 에 집어넣습니다.
    • 현재 비교하는 배열의 값보다 stack의 상단 요소 작으면, stack 의 요소를 하나씩 빼면서 크기를 비교합니다.
      • 현재 비교하는 배열의 값과 stack 요소가 같거나 큰 요소가 나올 때까지 빼줍니다.
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