[JAVA] Programmers <Stack_LV2> 주식 가격

...? 이해가 잘 안되는 문제였다. 처음엔 그저 stack하나를 선언해놓고 주식의 가격이 기준치부터 stack에 다음 가격과 비교하여 넣는 코드를 작성했다. 첫 코드는 이중 for 문 안에서 스택이 비었는지 확인하고, 비어있으면 스택을 하나 채운 뒤 다음에 올 가격과 비교 후, 가격이 같거나 올라갔을 경우 계속 우겨넣다가 가격이 떨어지는 순간, 스택의 크기를 측정하여 사이즈를 정답 배열에 넣어 완성했다. 

break도 없고 하나의 stack을 계속 지웠다 썼다 하니, 당연히 시간 초과가 나올 줄 알았으나, 첫번째 시도는 테스트 케이스 1(예시로 나온 케이스) 만 통과하고 나머지 19개의 테스트 케이스를 모조리 틀렸다. 

뭐...시간도 당연히 초과되었다.

 

두번째 코드는 stack을 null값으로 메모리를 미리 선언해놓고 계속 덮어 씌움으로써 clear() 하는 시간을 줄이고 중간에 빠져나올 수 있는 코드를 추가하여 돌렸다. 마찬가지로 이중 for 문을 포기할 수는 없어서 시간을 어떻게 줄이지..? 하는 순간...!

읭...? 이왜진; 

뭐...이렇게 쉽게 풀리는 걸 기대한 건 아니지만, 기분은 좋다.

 

Code: 

package com.choonham;

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stack = null;
        int len = prices.length;
        for(int i = 0; i < len; i++) {
        	stack = new Stack<>();
        	stack.add(prices[i]);
        	for(int j = i+1; j < len; j++) {
        		if(stack.get(0) <= prices[j]) {
        			stack.add(prices[j]);
        		} else {
        			answer[i] = stack.size();
        			break;
        		}
        		answer[i] = stack.size()-1;
        		
        	}
        }
    
        return answer;
    }
}