프로그래머스 - 주식 가격

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

프로그래머스

 

 

 

 

 

문제

• 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return

제한 사항

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

 

 

 

입출력 예시

• 입력 : prices [1, 2, 3, 2, 3]
• 출력 : [4, 3, 1, 1, 0]

 

 

 

 

 

풀이

n초 시점의 가격이 떨어지지 않은 기간을 알기 위해서는 뒤에 나오는 가격들과 비교해야 한다. 가장 먼저 떠오르는 방법은 배열을 순회하면서 이중 for문으로 비교하는 방법이다. 시간 복잡도는 O(n^2)이고, 문제의 제한 사항을 보면 길이가 100,000 이하이므로 최대 100,000 * 100,000 = 100,000,000,000 (1000억)이 걸린다. 시간초과가 날 것이다.

 

시간 복잡도를 낮춰야 하는데 자료 구조가 필요하다. 가격 비교를 하는 데, 관심사는 당장 다음에 올 가격이 현재 가격과 작은지 큰지이다. 그리고 계속 가격 정보를 쌓아나갈 필요가 있기 때문에 스택이 적합하다.

 

• 스택
  • 삽입, 삭제, 조회에 O(1) 시간이 소요된다. 따라서 문제에서는 O(n)이 소요될 것이다.
  • 스택에 prices의 인덱스를 넣는다 (가격의 정보는 인덱스를 통해서 알 수 있으므로 넣지 않는다.)
  • 현재 가격이 top에 있는 인덱스의 가격보다 작은지 비교한다.
    • 스택에서 제거하고, 정답에 초를 계산해서 저장한다.
    • 작으면 반복한다.
  • 끝나면 현재 가격의 인덱스를 스택에 넣는다.
  • n까지 다 보고 나면, 끝나고 나면 스택에 남아있는 주식 가격의 인덱스들이 있다.
    • 초 계산해서 정답에 저장한다.

 

 

 

 

백준의 스카이라인 쉬운거 문제(https://www.acmicpc.net/problem/1863)와 비슷하다.

 

 

 

 

 

코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        Stack<Integer> stack = new Stack<>(); //주식 가격 인덱스 저장
        int[] answer = new int[prices.length];
        
        for(int i = 0; i < prices.length; i++) {
            while(!stack.isEmpty() && prices[i] < prices[stack.peek()]) { //새로 들어오는 가격이 상단에 있는 가격보다 작음
                int idx = stack.pop(); //스택에서 빼서
                answer[idx] = i - idx; //초 계산해서 정답에 저장
            }
            
            stack.push(i); //스택에 넣기
        }
        
        //끝나고 나면 스택에 남아있는 게 있음
        for(int idx : stack) {
            answer[idx] = prices.length - 1 - idx; //초 계산해서 정답에 저장
        }
        
        return answer;
    }
}

 

 

 

 

결과

 

 

 

 

 

배운점

• 스택에서 빼낼 때, while(!stack.isEmpty() && 조건) 을 함께 주는게 좋음
• 스택에 남은 것을 처리해줘야 한다.