프로그래머스_스택/큐_주식가격 (JAVA)

 

문제 설명 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.   제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예   입출력 예 설명 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다. 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다. 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

 

스택/큐의 첫번 째 문제였던 탑 문제와 유사한 문제입니다. 얼핏 2중 반복문을 통해서 하나씩 찾아나가면 되는 것처럼 보이지만 다중반복문을 단순하게 돌리는 것이 정답인 문제는 없지 않을까 생각합니다. 특히 이런 유형의 경우 앞에서 자신보다 작은 숫자가 나올 때까지 뒤의 숫자들을 모두 찾고 다녀야 한다는 점에서(탑 문제는 반대) 역으로 생각해야 한번의 순회로 해결할 수 있습니다.

 

---

 

 

문제의 핵심은 뒷쪽에 자신보다 큰 숫자는 의미가 없고 처음 나오는 작은 숫자의 인덱스만 알면 된다는 것입니다. { 3, 5, 2, 1 } 의 배열을 예로 들면 가장 앞의 3은 자신보다 큰 5가 있건 없건 상관이 없고 2의 위치만 알면 된다는 것이죠.

 

뒤에서부터 순회를 할 때 앞쪽에 자신보다 작은 숫자가 앞에 있다면 자신은 굳이 스택에 들어가지 않아도 된다는 의미입니다. 그리고 마찬가지로 더 작은 숫자가 나와 스택에 쌓여있는 숫자들과 차례로 비교를 할 때 자신보다 큰 숫자를 모두 지워주면 됩니다. 뒷쪽에 자신보다 큰 숫자는 의미가 없기 때문입니다. 이 원리만 이해하면 로직을 짜는 것은 크게 어렵지 않을 것 같습니다.

 

package pojoPrj;

import java.util.Arrays;
import java.util.Stack;

class Solution {

	public static void main(String[] args) {

		int[] prices = new int[] { 1, 2, 3, 2, 3 };
		Solution s = new Solution();
		System.out.println(Arrays.toString(s.solution(prices)));

	}

	public int[] solution(int[] prices) {

		int[] answer = new int[prices.length];
		Stack<int[]> stack = new Stack<>();

		// 뒤에서부터 순회
		for (int i = prices.length - 2; i >= 0; i--) {

			// 앞쪽의 숫자가 뒷쪽의 숫자보다 클 경우
			if (prices[i] > prices[i + 1]) {

				answer[i] = 1;
				stack.push(new int[] { prices[i + 1], i + 1 });

			// 앞쪽의 숫자가 뒷쪽의 숫자보다 작거나 같은 경우
			} else {

				// 스택에서 자신보다 낮은 값이 나올때까지 모두 지워줌
				while (stack.size() > 0 && stack.peek()[0] >= prices[i]) {
					stack.pop();
				}

				// 스택이 빌 경우 (뒷쪽의 모든 값이 자신보다 큼)
				if (stack.size() == 0) {
					answer[i] = prices.length - i - 1;

				// 스택에 자신보다 낮은 숫자가 남아있다면 해당 인덱스와 자신의 인덱스를 이용해 계산
				} else {
					answer[i] = stack.peek()[1] - i;
				}
			}
		}

		return answer;
	}
}