[프로그래머스] - 주식가격 (스택/큐)
문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
- prices의 길이는 2 이상 100,000 이하입니다.
입출력 예
price | return |
---|---|
[1, 2, 3, 2, 3] | [4, 3, 1, 1, 0] |
- 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
- 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
- 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
- 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
- 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
문제 풀이
혼자서 문제를 이해하고 풀기 위해 고군분투 했으나 결국 다른 고수님들의 도움을 받기로 했다...
이중 for 문을 활용한 방법
- Python
def solution(prices):
answer = []
for i in range(len(prices)):
num = 0
for j in range(i+1, len(prices)):
num = num + 1
if prices[i] > prices[j]:
break
answer.append(num)
return answer
- Java
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
for(int i = 0; i < prices.length; i++) {
int num = 0;
for(int j = i+1; j < prices.length; j++) {
num = num + 1;
if(prices[i] > prices [j])
break;
}
answer[i] = num;
}
return answer;
}
}
Stack 을 활용한 방법
- Python
def solution(prices):
# answer = 몇초 후 가격이 떨어지는지 저장하는 배열
answer = [len(prices)-i-1 for i in range(len(prices))]
# stack = prices의 인덱스를 차례로 담아두는 배열
stack = [0]
for i in range(1, len(prices)):
while stack:
index = stack[-1]
# 주식 가격이 떨어졌다면
if prices[index] > prices[i]:
answer[index] = i - index
stack.pop()
# 떨어지지 않았다면 다음 시점으로 넘어감 (주식 가격이 계속 증가하고 있다는 말)
else:
break
# 스택에 추가한다.
# 다음 시점으로 넘어갔을 때 다시 비교 대상이 될 예정이다.
stack.append(i)
return answer
- Java
import java.util.Stack;
class Solution {
public int[] solution(int[] prices) {
int[] answer = new int[prices.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < prices.length; i++) {
while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
answer[stack.peek()] = i - stack.peek();
stack.pop(); // 답을 구했기 때문에 stack에서 제거
}
stack.push(i);
}
while (!stack.isEmpty()) { // 값을 구하지 못한 index == 끝까지 가격이 떨어지지 않은 주식
answer[stack.peek()] = prices.length - stack.peek() - 1;
stack.pop();
}
return answer;
}
}
Author And Source
이 문제에 관하여([프로그래머스] - 주식가격 (스택/큐)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jonnygim/프로그래머스-주식가격-스택큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)