[99클럽 코테 스터디 4일차 TIL] 프로그래머스 - 주식가격

체감 난이도 = 하

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

✏️ stack 사용

문제 분석

각 주식가격별로 자신의 가격보다 낮은 가격이 언제 나오는지 구해야합니다.
이런 종류의 문제는 스택을 이용하면됩니다.

설계

스택에 prices의 값과 인덱스를 넣습니다.
이번에 넣을 prices의 값과 스택의 탑에 있는 값을 비교합니다. 스택의 탑에 있는 값이 더 작으면 탑에서 pop하고, pop한 값의 인덱스(a)와 현재 prices에서 검사중인 인덱스(b)의 차이(b-a)를 정답 배열의 a번째 인덱스에 저장합니다.

코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        Deque<Info> stack = new ArrayDeque<>();
        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && stack.peekLast().price > prices[i]) {
                Info now = stack.removeLast();
                
                answer[now.idx] = i - now.idx;
            }
            
            stack.add(new Info(i, prices[i]));
        }
        
        while (!stack.isEmpty()) {
            Info now = stack.removeLast();
            answer[now.idx] = answer.length-1 - now.idx;
        }
      
        return answer;
    }
    
    class Info {
        int idx;
        int price;
        
        public Info (int idx, int price) {
            this.idx = idx;
            this.price = price;
        }
    }
}

코드 개선

다른 사람 풀이를 보고, 개선할 부분을 발견했습니다.

변경 사항

개선전에는 내부 클래스 Info를 만들어서 인덱스와 주식가격 값을 저장했었습니다.

그런데, 인덱스 정보만 있으면 주식가격값은 prices에서 가져올 수 있습니다. 배열에서 인덱스로 조회하는 동작도 O(1)이기 때문에, 만든 내부 클래스를 지우고 스택 타입을 Integer로 변경하여 인덱스 값을 저장하도록 변경했습니다.

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[stack.peekLast()] > prices[i]) {
                int idx = stack.removeLast();   
                answer[idx] = i - idx;
            }
            
            stack.add(i);
        }
        
        while (!stack.isEmpty()) {
            int idx = stack.removeLast();
            answer[idx] = answer.length-1 - idx;
        }
      
        return answer;
    }
}

결과적으로 개선 전과 개선 후의 코드가 효율성 측면에서 그렇게 차이나는 것 같지는 않으나, 개선 후 코드의 가독성이 더 좋습니다.