[프로그래머스] 주식가격

1. 문제

---

프로그래머스

2. 풀이 과정

---

• 이 문제는 언뜻보면 쉬워보이는 문제이다. 하지만 이 문제의 핵심은 최대 입력 크기가 10만이라는 점이다.
  즉, O(N^2)으로는 풀 수 없다는 뜻이다. O(N^2)으로 풀이 시 그냥 이중 for문을 사용하면 쉽게 구현할 수 있지만 이 문제는 O(N)으로 풀어야 한다.

• 그렇다면 어떻게 O(N)으로 구현할 수 있을까?

일단 이 문제를 확실하게 이해하고 갈 필요가 있다.

우선 결과 배열의 각 인덱스 값이 어떻게 결정되는지를 파악해야 한다.

 

이 문제의 핵심은 중간에 가격하락이 발생하는 경우이다.

 위 예제의  prices[3]에서 가격 하락이 발생한다.

 이 경우 가격 하락의 영향을 받은 인덱스인 2번 인덱스의 결과 값은 1로
 이 값은 가격하락이 발생한 인덱스 - 현재 인덱스이다.  

 

하지만 중간에 가격하락이 발생하지 않는 경우도 있다.

위의 예제의 prices[0], prices[1], prices[3], prices[4]의 경우이다.

이 경우엔 뒤에 가격하락을 발생시키는 인덱스가 등장하지 않으므로 답은 배열의 길이 - 현재 인덱스 - 1이 된다. 

 

하나씩 현재의 가격데이터를 이전 가격 데이터와 비교해서 가격하락이 발생하면 그 시점에 답이 결정되지만 끝까지 가격하락이 발생하지 않으면 끝까지 가야한다.

나는 현재 데이터와 이전 데이터를 비교하고 이 결과에 따라 어떠한 처리를 해야하는 구조를 보고 이전 데이터를 참조하기 좋은 스택을 떠올렸다.

 

이전 데이터와 비교해 가격 하락이 발생되지 않으면 스택에 인덱스를 넣고 하락이 발생되면 스택에서 인덱스를 꺼내 그 인덱스의 값을 확정시키는 식으로 구현할 수 있다. 그리고 스택에 남은 인덱스는 끝까지 가격하락이 발생하지 않은 것이므로 하나씩 꺼내 배열의 길이 - 현재 인덱스 - 1을 해서 인덱스의 값을 확정시키면 된다.

 

그림으로 보자

 

1. 가격 하락이 발생: prices[3]

 

• 0, 1, 2 까지는 가격하락이 발생하지 않으니 그대로 push
• 3에서 가격하락이 발생했으므로 이전 인덱스인 2 pop 후 답 확정짓기

2. 가격하락이 발생 X: prices[0], prices[1], prices[2], prices[4]

• 스택에서 인덱스를 하나씩 꺼내 답을 확정짓는다.

이제 코드로 구현해보자

3. 내 코드

---

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[prices.length];
        
        for(int i = 0; i < prices.length; i++) {
            // 가격 하락이 발생하지 않으면 스택에 푸시
            if(stack.isEmpty() || (prices[stack.peek()] <= prices[i])) {
                stack.push(i);
            }
            // 가격 하락이 발생하면 그 이전 인덱스의 답을 확정 짓고 pop
            else { 
                result[stack.peek()] = i - stack.peek();
                stack.pop();
                i--; // 가격 하락을 발생시킨 인덱스도 이후 다른 인덱스와의 비교를 통해 
                     //가격 하락 여부를 체크해야 하므로 하나 줄여줘서 다시 체크
            }
        }
        
        // 중간에 가격이 하락하지 않아 스택에 남은 인덱스들 답 확정 짓기
        while(!stack.isEmpty()) {
            result[stack.peek()] = prices.length - 1 - stack.peek();
            stack.pop();
        }
            
        
        return result;
    }
}

시간복잡도

• O(N)

4. 다른 정답 코드와 비교

---

[『코딩 테스트 합격자 되기 - 자바편』 해설 코드]

import java.util.Stack;

class Solution {

    public static int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n]; // ❶ 가격이 떨어지지 않은 기간을 저장할 배열

        // 스택(stack)을 사용해 이전 가격과 현재 가격 비교
        Stack<Integer> stack = new Stack<>(); // ❷ 스택 생성
        stack.push(0);

        for (int i = 1; i < n; i++) {
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                // ❸ 가격이 떨어졌으므로 이전 가격의 기간 계산
                int j = stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }

        // ❹ 스택에 남아 있는 가격들은 가격이 떨어지지 않은 경우
        while (!stack.isEmpty()) {
            int j = stack.pop();
            answer[j] = n - 1 - j;
        }

        return answer;
    }

}

시간복잡도

• O(N)

역시 스택을 통해 구현한 것을 알 수 있다.

5. 피드백

---

• 이 문제는 O(N^2)으로 풀었다면 쉽게 풀렸을 문제이지만 O(N)으로 풀어야 했기에 어려웠던 것 같다.
• O(N)으로 풀기 위해 스택을 떠올리는 과정이 쉽지 않았던 것 같다.
• 스택은 제일 최신의 데이터를 참고하기 좋은 자료구조라는 것을 명심하자