[프로그래머스/LV2] 주식가격 - stack (Java)

주식가격

🙋‍♂️ 아이디어

가격이 떨어지는 순간 길이를 계산해야해서, 값이 아닌, idx를 활용해야한다고 생각했다.

이에 단조 스택 형태로 구성하여 stack에 각 prices[i]의 idx를 추가하다가 stack이 안 비었고 stack의 마지막 원소를 활용해 prices[stack.peek()] > prices[i] 라면 길이 갱신

testcase 검증

------------ tc-1 ------------

prices = {1,2,3,2,3}
answer = {4,3,1,1,0}


idx : 0
val : 1
-> stack(0)


idx : 1
val : 2
-> stack(0, 1)


idx : 2
val : 3
-> stack(0, 1, 2)


idx : 3
val : 2
-> 스택 안비었고, arr[stack.peek()] > arr[i] 즉 arr[2] > arr[3] 일치하기에 pop으로 추출하고 길이 계산
arr[idx] = i - idx 즉 arr[2] = 3-2, stack(0,1)이 되었고, 스택이 안비었기에 이어서 재검사
arr[stack.peek()] > arr[i] 은 arr[1] > arr[3] 즉 2 > 2라서 해당사항이 없기에 while문을 종료하고 stack에 추가한다
stack(0, 1, 3)


idx : 4
val : 3
-> 스택이 안비었고 arr[stack.peek()] > arr[i] 즉 arr[3] > arr[4] 라 2 > 3 이라서 while문 해당사항이 없고 stack에 추가한다
stack(0,1,3,4)


결론
-> arr[2] = 1 완성
나머지 4개는 남아서 stack이 비지 않을 때 까지 처리해야겠다
idx = stack.pop();
arr[idx] = N-1-idx;

------------ tc-2 ------------

prices = {1,3,2,3,6,4,5,2,1}
answer = {8,1,6,4,1,2,1,1,0}

위와 같은 과정으로 하면
prices[0], prices[8]이 남아서
stack(0, 8) 이 남을 것이다

마찬가지로 stack이 비지 않을 때 까지 계산해준다

✅ 정답 코드

class Solution {
    public int[] solution(int[] prices) {
        int N = prices.length;
        int[] answer = new int[N];
        
        // 1. 판별기
        int[] res = my_converter(prices, N, answer);
        return res;
    }
    
    // 2. my_converter 함수
    static int[] my_converter(int[] prices, int N, int[] answer) {
        
        // 2-1. my_stack 객체 생성
        my_stack stack_v1 = new my_stack(N);
        
        // 2-2. 길이 계산을 위해 stack에는 값이 아닌, idx를 저장하자 
        // 각 가격 기준, stack의 last_idx 가격보다 작으면 stack.pop
        // 그리고 arr[last_idx] = i - last_idx
        
        for (int i = 0; i < N; i++) {
            int cur_price = prices[i];
            
            // 2-2-a. 스택이 비어있지않고 && prices[stack_v1.peek()] 가격보다 작으면 stack.pop
            while (!stack_v1.isEmpty() && cur_price < prices[stack_v1.peek()]) {
                int idx = stack_v1.pop();
                answer[idx] = i - idx;
                
            }
            // 2-2-b. stack에 현재 idx 추가
            stack_v1.push(i);
        }
        
        // 2-3. stack에 남은 idx 계산
        while (!stack_v1.isEmpty()) {
            int idx = stack_v1.pop();
            answer[idx] = N - 1 - idx;
        }
        
        // 2-4. 결과값 반환
        return answer;
    }
    
    
    
    // 3. my_stack 클래스
    static class my_stack {
        
        // 3-1. 데이터 상태 정의
        private int top;
        private int[] stack_v1;
        
        // 3-2. my_stack 생성자
        my_stack(int size) {
            top = -1;
            stack_v1 = new int[size];
        }
        
        // 3-3. push
        void push(int value) {
            top++;
            stack_v1[top] = value;
        }
        
        // 3-4. pop
        int pop() {
            int value = stack_v1[top];
            top--;
            return value;
        }
        
        // 3-5. peek
        int peek() {
            int value = stack_v1[top];
            return value;
        }
        
        // 3-6. isEmpty
        boolean isEmpty() {
            if (top != -1) return false;
            return true;
        }
        
        // 3-7. size
        int size() {
            return top + 1;
        }
        
    }
    
}

tc-2 검증

int[] test_prices = new int[] {1,3,2,3,6,4,5,2,1};
int test_N = test_prices.length;
int[] test_answer = new int[test_N];
int[] test = my_converter(test_prices, test_N, test_answer);
System.out.println(Arrays.toString(test));


        // 2-3. stack에 남은 idx 계산
        while (!stack_v1.isEmpty()) {
            int idx = stack_v1.pop();
            System.out.println(idx);
            answer[idx] = N - 1 - idx;
        }

출력값

8
0
[8, 1, 6, 4, 1, 2, 1, 1, 0]

역시 stack에 idx 0, 8이 남았고 answer과 동일하게 나왔다