[스택/큐] 주식가격 - Java 코드 ★★★

https://programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격

 

문제

 

이해

각 원소의 유지되는 시간은 한 인덱스당 1초이다.

마지막 원소의 유지시간은 무조건 0이다.

 

배열을 사용한 풀이

완전탐색을 이용하면 보다 직관적이고 수월하다.

class Solution {
    public int[] solution(int[] prices) {
        // 완전탐색은 n2 순회
        int[] res = new int[prices.length];
        for(int i=0;i<prices.length-1;i++){
            for(int j=i+1;j<prices.length;j++) {
                res[i]++;
                if (prices[i] > prices[j])
                    break;
            }
        }
        return res;
    }
}

 

 

Stack을 이용한 풀이

/*
정확성  테스트
테스트 1 〉    통과 (0.16ms, 77.5MB)
테스트 2 〉    통과 (0.34ms, 81.6MB)
테스트 3 〉    통과 (1.65ms, 83.4MB)
테스트 4 〉    통과 (1.39ms, 79.1MB)
테스트 5 〉    통과 (1.85ms, 80MB)
테스트 6 〉    통과 (0.20ms, 75.3MB)
테스트 7 〉    통과 (0.87ms, 71.8MB)
테스트 8 〉    통과 (0.99ms, 78MB)
테스트 9 〉    통과 (0.21ms, 73.5MB)
테스트 10 〉   통과 (1.64ms, 68.9MB)
효율성  테스트
테스트 1 〉    통과 (77.02ms, 73.2MB)
테스트 2 〉    통과 (28.31ms, 63.4MB)
테스트 3 〉    통과 (39.27ms, 76.3MB)
테스트 4 〉    통과 (32.34ms, 71.2MB)
테스트 5 〉    통과 (25.90ms, 66.7MB)
*/

import java.util.Stack;
class Solution {
	public int[] solution(int[] prices) {
        // 스텍을 이용해 O(n)순회
        int[] res = new int[prices.length];
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < prices.length; i++) {
            while (!st.isEmpty() && prices[st.peek()] > prices[i]) {// 가격이 떨어졌다면,
                res[st.peek()] = i - st.peek(); // 숫자를 기록한다.
                st.pop();
            }
            st.push(i);
        }
        while (!st.isEmpty()) {
            res[st.peek()] = prices.length - 1 - st.peek();
            st.pop();
        }
        return res;
    }
}

 

Stack에 번호를 넣어두고 해당 Peek값에 해당하는 배열값을 비교하여 초기화를 해간다.

초기화 되지 않은 값들은 배열의 길이 - 해당번째를 빼주어 값을 초기화 해준다.