[ Stack, Queue / 스택, 큐 ] - 주식 가격(배열, 스택,

문제

초 단위로 기록된 주식가격이 담긴 배열 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 < answer.length; i++) {
			for(int j = i + 1; j < answer.length; j++) {
				answer[i]++;
		              
				if(prices[i] > prices[j]) {
					break;
				}
			}
		}
        return answer;
    }
}

풀이

1. 특정 시점(i)과 그 이후의 시점(j)들의 가격을 비교해서 떨어지지 않은 시간을 1초씩 증가
2. 만약 떨어지면(특정시점값과 그이후의 값 비교) 종료(break)

2. 큐

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++){
        	// 최대기간으로 세팅
            answer[i] = answer.length - 1 - i;
            // 인덱스, 가격
            //[0, 1]
            //[1, 2]
            //[2, 3]
            //[3, 2]
            //[4, 3]
            Integer[] arr = {i, prices[i]}; 
            // 가격이 떨어진 경우(스택의 상단 값과 다음 인덱스arr에 들어갈 값 비교)
            while(!stack.empty() && stack.peek()[1] > prices[i]){
            	// [2,3]
                Integer[] price = stack.pop();
                // answer[2] = 3-2
                // 떨어진 값 인덱스 - 떨어지기 전 인덱스 값으로 계산하여 얼마만큼의 시간만큼 떨어진지 알수있다.
                answer[price[0]] = i - price[0];
            }
            stack.push(arr);
        }
        return answer;
    }
}

 

풀이

1. 가격이 떨어지지 않은 기간의 초를 return하는 거므로 초 단위로 기록된 주식가격만큼의 길이가 정해져있어 배열로 초기화한다.

2. 그리고 배열의 순서대로 Stack에 쌓는데,

3. 최대 기간으로 세팅, 배열생성하여 인덱스와 가격을 넣는다.

4. 넣기 전, 이전 값의 가격과 현재 넣으려는 값의 가격을 비교하여(가격이 떨어졌는지를 알 수 있다.) 떨어진 경우 인덱스 값 만큼 빼준다.

5. Stack에 쌓는다.

 

3. 스택

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public static int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Queue<Integer> q = new LinkedList<>();
        // 1, 2, 3, 2, 3
        for (int i : prices) {
            q.add(i);
        }
 
        int index = 0;
        while (!q.isEmpty()) {
            int currentPrice = q.poll();
            // currentPrice의 다음 가격부터 반복문을 진행 = i = (prices.length - q.size()
            for (int i = (prices.length - q.size()); i < prices.length; i++) {
                // 가격이 떨어 졌을 경우
                if (currentPrice > prices[i]) {
                    answer[index]++;
                    break;
                }
                // 가격이 떨어지지 않았을 경우
                if (currentPrice <= prices[i]) {
                    answer[index]++;
                }
            }
            index++;
        }
        return answer;
    } 
}

 

풀이

1. 또 다른 Queue의 방식으로 풀어논 코드이다. 근데 배열과 동작하는 방식이 비슷하다고 본다. 그리고 for문에서 시작 인덱스를 그냥 1로 줘도 문제가 없어보이긴한다.