[프로그래머스 , 자바] Level2: 주식가격

 

문제분석:

 

문제 목표 : 각 시간대별로 주식이 떨어지지않는 시간을 구하자

 

이 문제를 풀기에 앞서....

 

이 문제는 스택/큐로 푸는게 맞습니다.   하지만 2중반복문으로 풀리는게  참으로 이상합니다.

 

 

사실 2중반복문으로 생각해서 푸는게 제일로 쉽습니다.

거의 Level1 수준으로 말이죠.

 

그냥 단순하게

1초일때 주식가격 을 n번 돌려서 깍이는 구간을 확인하고

2초일때 주식량을 n번 돌면서 깍이는 구간확인하고 

3초일때 .... 하면 n^2걸려서 구합니다.

 

 

근데 문제제약을 보면 prices의 길이가 10만입니다.

 

최대 n^2이 걸리는 문제를 10만^2을 하면 무려 100억번입니다. 

 

근데 이 문제가 2중반복문으로 구현하면 풀립니다. 심지어 효율성테스트도 스택보다 빠릅니다

(아니..대체 왜..??)

 

2중 반복문일경우

스택일경우

바뀐거 아닙니다. 진짜로 이럼

 

아마도 테스트케이스가 별로 크지않은경우같습니다.  제약조건이 틀린것같습니다 단순하게

 

 

 

이 문제를 스택으로 푸시면  O(2n)의 시간복잡도가 걸려 최대 20만번입니다.

100억번 vs 20만번 당연히 후자가 더 효율적이죠

 

 

그래서 이번 문제는 스택으로 풀이해보겠습니다.

 

 

1. 먼저 모든 prices를 스택에 넣기

 

모든 주식의 price를 넣습니다.

 

하지만 넣을때 조건이 하나들어갑니다. 

 

만약, stack.peek() {이전값}이  들어가는값보다 크면 스택에서 뽑아야합니다.

그 이유는, 나중에 스택에 남아있는 요소들은  단순하게 전체길이- 입력이됬던idx로 쉽게구해집니다.

 

스택이 뽑혓을때, 뽑힌값의 시간도 구해줘야합니다.

 

뽑혓을때 시간은,  현재 idx - 입력됫을때의 idx 를하시면 쉽게 구할수있습니다.

 

<여기까지 O(n)의 시간>

 

2. 스택에 남아있는 요소들 순회  

 

1번에서 설명했듯이,  뽑히지 않는 요소들을 하나씩 뽑아내어 

 

전체 기록의 길이 - 입력됫을때 idx를 하여 시간을 구해 저장합니다.

<여기까지 O(n)>

 

 

따라서 2n의 시간으로 구현이 가능합니다.

 

문제풀이

import java.util.*;
class Solution {
public int[] solution(int[] prices) {
 
    int[] answer = new int[prices.length];
 
    Stack<Integer[]> s= new Stack<>(); 
 
    for(int i=0;i<prices.length;i++){
 
        Integer[] tmp = {prices[i],i};
 
        if(s.empty()){
 
            s.push(tmp);
 
            continue;
 
        }
 
        else{
 
            while(s.peek()[0]>prices[i]){
 
                answer[s.peek()[1]]=i-s.peek()[1];
 
                s.pop();
 
                if(s.empty())
 
                    break;
 
            }
 
        }
 
        s.push(tmp);
 
    }
 
    while(!s.empty()){
 
        answer[s.peek()[1]]=prices.length-1-s.peek()[1];
 
        s.pop();
 
    }
 
    return answer;
 
}
}