주식가격

---

💡 문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

💡 제한 조건

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

🔑 입출력 예

prices	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초간 가격이 떨어지지 않았습니다.

---

📌 문제 해석

처음 문제를 봤을 때 단번에 이해가 되지 않았다..😂 내 독해 실력에 의심을 품고, 천천히 몇 번 읽어보니 그제야 이해가 됐다.

그림으로 표현해 보면, 1초 간격으로 주식 가격의 변화를 배열로 주고, 가격이 떨어지지 않은 기간을 배열로 return 하는 문제였다.

이중 for문을 활용하면 쉽게 풀 수 있는 문제였지만, 도저히 Stack으로는 어떻게 풀어야할지 감이 잡히지 않았다.
크롤링을 통해 다른 분들의 풀이를 분석해봤지만, (참고 링크) 잘 이해가 되지 않아. 직접 그림을 그리면서 풀어보았다.

🔗 Stack과 Queue정리 https://velog.io/@imok-_/Stack과 Queue

---

💻 작성 코드 1 - java

이중 for문 활용

class Solution {
	public int[] solution(int[] prices) {
		int[] answer = new int[prices.length];

		for (int i = 0; i < prices.length; i++) {
			for (int j = i + 1; j < prices.length; j++) {
				answer[i]++; // 뒤에 있는 값들 보다 작거나 같을 때 인덱스 값 하나씩 추가
				if (prices[i] > prices[j]) { // 크면 다음 인데스 비교
					break;
				}
			}
		}
		return answer;
	}
}

---

💻 작성 코드 2 - java (Stack 활용)

1. Stack 생성

class Solution {
	public int[] solution(int[] prices) {
		int[] answer = new int[prices.length];
		Stack<Integer> stack = new Stack<>(); // stack 생성

2. for문 돌면서 주식이 떨어졌을 경우 answer에 넣고, 증가하거나 동일할 경우 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.push(i);
		}

2-1. prices[stack.peek()] 과 비교해 주식이 증가하거나 동일할 경우, stack에 index를 push한다.

while (!stack.isEmpty() && prices[i] < prices[stack.peek()])

1. !stack.isEmpty()

   처음에 stack이 비어있으므로 false
   stack.push(0);

2. prices[i] < prices[stack.peek()] // i = 1, stack.peek()은 직전에 넣었던 index인 0

   prices[1] < prices[0]
   2 < 1 => false
   stack.push(1);

3. prices[i] < prices[stack.peek()] // i = 2, stack.peek()은 직전에 넣었던 index인 1

   prices[2] < prices[1]
   3 < 2 => false
   stack.push(2);

2-2. 감소하는 값이 등장하면, 감소한 시점의 answer에 i - stack.peek()을 넣어주고, 그 인덱스를 stack에서 pop한다.

4. prices[i] < prices[stack.peek()] // i = 3, stack.peek()은 직전에 넣었던 index인 2

   prices[3] < prices[2]
   2 < 3 => true

   answer[stack.peek()] = i - stack.peek();

   answer[2] = 3 - 2 = 1
   stack.pop(); // 2

   stack.push(3);

2-3. prices[stack.peek()] 과 비교해 주식이 증가하거나 동일할 경우, stack에 index를 push한다.

5. prices[i] < prices[stack.peek()] // i = 4, stack.peek()은 직전에 넣었던 index인 3

   prices[4] < prices[3]
   3 < 2 => false
   stack.push(4);

3. answer에 값 담음

• stack에 있는 값은 끝까지 주식 가격이 떨어지지 않은 경우이므로, stack이 비어있을 때까지 prices.length - index -1을 넣어준다.

		while (!stack.isEmpty()) {
			answer[stack.peek()] = prices.length - stack.peek() - 1;
			stack.pop();
		}
		return answer;

answer[stack.peek()] = prices.length - stack.peek() - 1;

answer[4] = 5 - 4 - 1 = 0;
answer[3] = 5 - 3 - 1 = 1;
answer[1] = 5 - 1 - 1 = 3;
answer[0] = 5 - 0 - 1 = 4;

최종 answer = [4, 3, 1, 1, 0]

4. 최종 소스

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.push(i);
		}

		while (!stack.isEmpty()) {
			answer[stack.peek()] = prices.length - stack.peek() - 1;
			stack.pop();
		}
		return answer;
	}
}

---

🔗 문제 링크

[프로그래머스 - 주식가격]
https://programmers.co.kr/learn/courses/30/lessons/42584