[스택/큐] 주식가격

문제 설명

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

제한사항

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

입출력 예

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

문제 풀이 1) Brute Force

1: 2, 3, 2, 3 => 끝까지 가격이 떨어지지 않음. => 총 4초동안 가격 하락 X

2: 3, 2, 3 => 끝까지 가격이 떨어지지 않음. => 총 3초동안 가격 하락 X

3: 2 => 1초 후 가격이 2로 떨어짐. => 총 1초동안 가격 하락 X

2: 3 => 끝까지 가격이 떨어지지 않음. => 총 1초동안 가격 하락 X

3 => 마지막 값이라 0초동안 가격 하락 X

 

이중 for문을 이용해 문제를 풀었습니다.

현재 값이 뒤 인덱스 번호에 있는 값보다 작거나 같을 때는 answer 배열의 해당 인덱스 값을 하나씩 올려주고,

뒤 인덱스 번호에 있는 값보다 커지면 break 구문이 실행되어 반복문을 벗어나 다음 값이 비교되도록 합니다.

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

 

이중 for 문으로 풀었으므로 최악의 경우 시간 복잡도는 O(n^2) 입니다.

주어진 prices 길이의 최대값이 100,000 이면, 즉 입력값 n이 100,000 이므로 최악의 경우 총 연산횟수는 100억입니다.

보통 n이 1억 정도면 1초의 시간이 걸린다고 합니다. 

이에 따라 최악의 경우 100초의 시간이 걸릴 수 있습니다.

문제 풀이 2) Stack

이 문제가 스택/큐로 분류되어 있어 스택을 이용해 문제를 풀고자 했지만 도저히 아이디어가 떠오르지 않아 프로그래머스 다른 사람의 풀이, 구글링을 참고하여 풀이를 찾아보고 코드를 이해하려 노력했습니다.

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n];
        // 주식가격 변화가 없는 시간대 저장
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && prices[stack.peek()] > prices[i]) {
                int pop = stack.pop();
                answer[pop] = i - pop;
                
            }
            stack.push(i);
        }
        
        while (!stack.isEmpty()) { // stack에 저장된 index == 끝까지 가격이 떨어지지 않은 주식
          int pop = stack.pop();
          answer[pop] = n - pop - 1;
        }
        return answer;
    }
}

 출처

문제 소스 : https://school.programmers.co.kr/learn/courses/30/lessons/42584 

풀이2 참조 : https://girawhale.tistory.com/7