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

문제 : programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class StockPrice {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];

        // initialize
        Stack<Integer> stocks = new Stack<Integer>();
        List<Integer> done = new ArrayList<Integer>();
        for (int price : prices) {
            stocks.push(price);
        }

        while (!stocks.isEmpty()) {
            int currentStock = stocks.pop();
            int stocksSize = stocks.size();
            int doneSize = done.size();

            for (int i = doneSize - 1; i >= 0; i--) {
                int comp = done.get(i);

                if (currentStock > comp) {
                    answer[stocksSize] = doneSize - i;
                    break;
                }
            }

            if (answer[stocksSize] == 0) {
                answer[stocksSize] = doneSize;
            }

            done.add(currentStock); 
        }
        return answer;
    }
}

 

Review

비교적 간단하게 구현할 수 있는 문제로 보인다.

사실 굳이 prices도 별도의 stack에 담지 않아도 될 것 같지만, stack에 담아서 계산하는 쪽이 좀 더 직관적으로 보일 것 같아서 위처럼 작성하였다.

 

처음에는 done 또한 Stack으로 구현하고, while문 내부에서 done을 clone 하여 사용했었는데, object 생성의 로드가 생각했던 것 보다 커서 효율성 체크에서 모두 시간 초과가 되었다. 

이에, 불필요하게 element를 stack에서 push & pop 하지 않도록 done을 Stack 에서 List로 수정하고, 값에 접근만 하는 형식으로 수정하였다.

List로 구현하였어도 마찬가지로 Stack 처럼 사용하기 위해 for문 내부에서 List의 head에서 시작하지 않고 tail에서부터 시작하도록 설정하였다. 이 과정에 의해 head부터 for문을 돌릴 경우 발생하는 매번 element를 뒤로 밀어주는 과정에서 생기는 비효율적인 동작도 제거할 수 있다.