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

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

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

import java.util.Stack;
class Solution {
		class Info{
			int num,time,index;
			public Info(int index,int num, int time) {
				this.index=index;
				this.num = num;
				this.time = time;
			}
			
		}
	    public int[] solution(int[] prices) {
	        int[] answer = new int[prices.length];
	        
	        Stack <Info> stack = new Stack<>();
	        int time=0;
	        
	        for(int i=0; i<prices.length; i++) {
	        	time++;
	        	int price=prices[i];
	        	if(stack.isEmpty()) stack.push(new Info(i,price, time));
	        	else { //안비어있으면
	        		while(true) {
	        			if(stack.isEmpty() || stack.peek().num<=price) {
	        				stack.push(new Info(i,price,time));
	        				break;
	        			}
	        			else if(stack.peek().num>price) {
	        				Info end=stack.pop();
	        				answer[end.index]=time-end.time;
	        			}
	        		}
	        	}
	        }
	        
	        while(!stack.isEmpty()) {
	        	Info end=stack.pop();
	        	answer[end.index]=time-end.time;
	        }
	        return answer;
	    }
	}

소요시간 : 20분

 

스택을 활용하면 쉬운 문제입니다.

 

로직을 살펴보면

 

1. 스택이 비어있다면 Info( 인덱스 , 가격, 스택에 들어간 시간)를 push 해줍니다.

2. 스택이 비어있지 않다면 

    2-1. 스택의 맨 위의 값보다 현재 가격이 더 크다면 스택에서 pop을 해줍니다. (반복)

    2-2. 스택의 맨위의 값보다 현재 가격이 더 크지 않거나, 스택이 비었다면 현재 price를 스택에 push 해줍니다.

3. 모든 price에 대해 1,2, 번을 수행했다면 스택이 비어있을 때까지 뽑아줍니다.

 

시간을 구하는 방법은 

현재 시간 - 스택에 들어간 시간을 해서 구했습니다~