[프로그래머스 / JAVA] 주식 가격 (정답 풀이)

자바 공부와 코딩테스트 준비를 병행할 겸 자바로 코테 준비를 며칠 전 시작했다.

막히거나 틀린 부분이 있더라도, 그냥 그대로 내가 스스로 작성한 부분들을 기록해 두려고 한다. 
그냥 미래의 복기용으로 나를 위해 적어둔 기록이다.
(이 사람은 어떻게 실패하거나 성공했는지 살펴보는 용도로도 적합할 것 같다.)
 
이 문제도 처음 봤을 때, 풀이를 떠올리지 못해 설명을 참고했다.
제약 조건인 prices의 길이가 최대 100,000이라 O(N^2)으로 구현(이중 for 문)하면 안 된다는 생각은 할 수 있었다.
 
처음 내가 스스로 구현했던 방법은 앞(오른쪽)이 아니라 뒤(왼쪽)에서부터 순회하는 방식이었다.
현재 순회하고 있는 인덱스의 주가가 바로 오른쪽에 있는 인덱스(바로 이전에 순회)의 값보다 크면, 즉, 주가가 낮아진 상황이라면 낮아진 시점을 기준으로 기간을 1씩 더해서 집어넣겠다는 생각이었다.
 
그러나 이는 잘못된 생각이라는 것을 알 수 있었다.
현재 시점의 바로 오른쪽 시점의 주가(A)는 높지만, 더 오른쪽 시점(B)에서 주가가 떨어지는 경우가 있을 수 있다.
이렇게 되면 시점 B에 의해서 기간이 결정되어야 한다.
하지만 내 코드는 바로 인접한(A) 시점의 주가와만 비교된다.
 
주가가 [4 5 4 5 3] 이런 상황이면, 5는 4에 의해(기간: 1), 4은 3(기간: 4)에 의해 기간이 결정되는데, 내 방식대로 하면 그냥 1이 더해진다. 그냥 논리적으로 아예 맞지 않는 생각이었다.
 
해설에서는 스택을 사용하라고 알려주었다.
나는 해설을 한 번 읽은 상태긴 하다. 그런데 이걸 내 스스로 다시 풀어내려니 몇 번이고 글을 지웠다 썼다 하게 된다.
아직 문제의 소화가 덜 된 느낌이다.
 
일단 핵심 아이디어는 이렇다.
한 시점의 주가(A)에 대해서 "가격이 떨어지지 않은 기간"이 확정되는 시점은, 제일 처음 더 낮은 주가를 마주했을 때다.
한 번 기간이 확정되고 나면 이후 더 볼 필요가 없다. 이후에는 나머지 결정 안된 애들(방금보다 더 낮은 주가들)만 남기고 생각하면 된다.
 
그래서 주가를 왼쪽부터 순회하면서 해당 주가의 "인덱스"를 스택에 쌓아오다가, 낮은 주가를 만나면 확정시킬 애들은 스택에서 꺼내서 확정시키고, 진짜 낮은 애들만 스택에 남겨두고 계속 진행시키면 된다.
 
나도 나중에 깨닫게 된 사실이지만, 스택에는 결국 인덱스뿐만 아니라, 주가도 아래에서부터 오름차순(주가가 동일할 수는 있음)으로 정렬되게 된다.
더 낮은 주가를 만나는 순간 스택에서 꺼내지기 때문이다. 결국 스택 꼭대기에는 주가가 크거나 같은 애들만 쌓일 수 있다.
 
아무튼 이런 내용들을 메모해놓고 싶었다.
아래는 내가 해설을 읽고 구현해 본 코드이다.

import java.util.ArrayDeque;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length]; //가격이 떨어지지 않은 기간을 기록할 배열
        ArrayDeque<Integer> stack = new ArrayDeque<>(); //stack으로 사용
        stack.push(0); //인덱스 0 저장
        
        for (int i = 1; i < prices.length; i++) { //1번 인덱스부터 순회
            if (prices[stack.peek()] <= prices[i]) { //현재 순회하고 있는 인덱스의 주가가 스택의 맨 위(스택의 주가 중 제일 높음)보다 같거나 높으면
                stack.push(i);
            } else { //prices[stack.peek()] > prices[i]
                while(!stack.isEmpty() && prices[stack.peek()] > prices[i]) { //기간 확정시킬 수 있는 스택의 요소들은 확정시키기(현재 순회하고 있는 인덱스의 주가가 더 낮으므로, 이 시점까지의 구간 길이를 구하면됨) 
                    int topIdx = stack.peek();
                    answer[topIdx] = i - topIdx;
                    stack.pop();
                }
                stack.push(i); //결국 얘도 스택에 들어가서 뒤따라 올 주가에 의해 기간이 결정되길 기다려야 함
            }
        }
        
        while(!stack.isEmpty()) { //아직도 스택 안에 있는 애들은 주가가 더 낮아진 상황을 안 마주한 애들임. 측정 마지막 시점까지로 구간을 설정하면 됨. 
            int topIdx = stack.peek();
            answer[topIdx] = prices.length - 1 - topIdx;
            stack.pop();
        }
        return answer;
    }
}

 
하루에 한 문제 이상 꾸준히 풀자.

실수는 많이 할수록, 더 많이 배울 수 있다.
 
https://school.programmers.co.kr/learn/courses/30/lessons/42584?language=java

프로그래머스