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