프로그래머스 - 주식가격

첫시도(오답)
처음에는 이렇게 풀었다.
가격 배열에서 다음 가격이 들어가면 그 앞의 모든 가격들에 대해, 시간계산이 끝난 가격은 skip시키고, 안끝난 가격은 시간을 ++해주고, 그 다음 새로온 가격보다 작으면 시간계산을 끝내주었다.
arr[][0] = 가격
arr[][1] = 시간
arr[][2] = 시간계산이 끝났는지 여부(자신보다 낮은 가격이 들어오면 끝남)

class Solution {
    public int[] solution(int[] prices) {
        int[][] arr = new int[prices.length][3];
        for(int i = 0; i < prices.length; i++){
            arr[i][0] = prices[i];
        }
        for(int i = 1; i < prices.length; i++){
        	//새로들어온 가격(i) 앞의 모든 가격들(j)에 대해
            for(int j = 0; j < i-1; j++){
            	//시간계산이 끝났으면 continue
                if(arr[j][2] == 1){
                    continue;
                }
                //시간++
                arr[j][1]++;
                //새로들어온 가격(i)이 더 낮으면 이 가격(j)은 시간계산 끝
                if(arr[j][0] > arr[i][0]){
                    arr[j][2] = 1;
                }
            }
        }
        //(위에서 실행하지 않은)마지막 가격이 들어왔을때 한 번을 마저 실행
        for(int i = 0; i < prices.length-1; i++){
            if(arr[i][2] == 1){
                continue;
            }
            arr[i][1]++;
        }
        int[] answer = new int[prices.length];
        for(int i = 0; i < prices.length; i++){
            answer[i] = arr[i][1];
        }
        return answer;
    }
}

이상하게 답이 나오지 않았다. 시간도 거의 1시간 이상을 썼다.

정답 풀이
틀린 이유도 더 이상 모르겠고, 효율성 검사도 실패로 나와 결국 그냥 포기하고 다른 풀이를 찾았다.
사실은 스택문제이기도하고, 이전에 풀었던 백준의 "탑" 문제와 굉장히 유사하다고 처음부터 생각했었다. 근데 당시 굉장히 힘들게 풀었어서 그 풀이 방법을 외면했는데, 이젠 그 방법밖에 안 남았기 때문에 그 쪽으로 생각을 한 번 시도해보았다.
그런데 생각보다 금방 풀이 방법이 떠올랐다.

• 이번 차례에 넣을 가격이 Stack의 top의 가격보다 작으면, top을 pop() 해버린다.
• 그리고 Stack에 남아있는 가격들의 시간을 모두 증가시켜준다.
• 현재 차례의 가격을 Stack에 push()한다.
  주어진 배열의 가격들에 대해 순서대로 이를 반복한다.

import java.util.*;
class Solution {
    public int[] solution(int[] prices) {
        //첫번째 숫자 push()
        //다음 숫자가 주어짐
        //모든 element 시간++
        //stack.peek()가 더 크면 pop해버림 - 반복(더 크지 않거나, stack.isEmpty() 까지
        //주어진숫자 push()
        Pair[] pairs = new Pair[prices.length];
        for(int i = 0; i < prices.length; i++){
            pairs[i] = new Pair(prices[i], 0);
        }
        Stack<Pair> stack = new Stack<>();
        stack.push(pairs[0]);
        for(int i = 1; i < prices.length; i++){
            for(Pair tmp : stack){
                tmp.time++;
            }
            Pair nowPair = pairs[i];
            while(!stack.isEmpty()){
                if(stack.peek().prices > nowPair.prices){
                    stack.pop();
                }else{
                    break;
                }
            }
            stack.push(nowPair);
        }
        int[] answer = new int[prices.length];
        for(int i = 0; i < prices.length; i++){
            answer[i] = pairs[i].time;
        }
        return answer;
    }
    static class Pair{
        int prices;
        int time;
        Pair(int prices, int time){
            this.prices = prices;
            this.time = time;
        }
    }
}

방법을 바꾸고 20분만에 풀었다. 이제 이 유형의 스택문제는 쉽게 해결할 수 있을 것 같다.