[코딩테스트] 주식가격 JAVA (Stack, 이중for문)

문제 설명
초 단위로 기록된 주식가격이 담긴 배열 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. 이중반복문으로 풀기 

class Solution {
    public int[] solution(int[] prices) {
            int[] answer = new int[prices.length];
            for(int i=0; i<prices.length -1 ; i++) {
                for (int j = i + 1; j < prices.length ; j++) {
                        answer[i]++;
                        if(prices[i]>prices[j]){ // 전보다 후의 수가 적으면 가격이 떨어진 것 
                            break; //그만 돌리고 다음 인덱스로 
                        }
                }
            }
            return answer;
    }
}

 

2. stack으로 풀기 

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;
	}
}

사실 이해가 잘 안되니 하나씩 해보자.

 

첫번째 반복문 : 

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);
}

i	0	1	2	3	4
p (prices)	1	2	3	2	3
a (answer)	0	0	0	0	0

1) i = 0 

stack 이 아직 비어있으므로 while문을 안타고  i를 stack 에 넣어줌

0

 

 2) i = 1 

p[1] < p[0]  

전에 것 보다 다음 것이 크면 가격 방어 성공!

전에 것이 더 크면 실패 

 2 < 1   

false 가격 방어 성공!

i stack 쌓음  -> 

1

0

 

3) i = 2

p[2] < p[1] 

3 < 2

false

2

1

0

 

4) i = 3

p[3] < p[2]

2< 3 

후에거 < 전에거 

전에보다 가격 떨어진것 

true 

a[2] = 3 - 2 

pop 2 꺼냄

1

0

stack.push(3)

3

1

0

 

 5)i = 4

p[4] < p[3]

3 < 2 

false

push 4

4

3

1

0

 

두 번째 반복문 : 

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

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

answer[3] = 5 - 3 - 1 = 1

 

아니 이 문제를 보고 어떻게 스택을 저렇게 활용하는 방법이 나오는지 도저히 머리가 돌아가지 않는다. 

너무 어려운거 아니요 ㅠㅠ