[프로그래머스,Java] Level2: 뒤에 있는 큰수

 

문제분석:

 

아주 간단한문제다

각 인덱스마다 뒤에있는 더 큰 숫자를 반환하고, 없으면 -1를 반환하면 간단한 문제이지만..

 

제한사항을 보면 길이가 100만이다.

이걸 보고 빠르게 2차반복문으로 쉽게 풀생각을 접어야한다.

 

 

어떻게든 1차 반복문으로 문제를 해결하자.

 

1차반복문으로 해결하려면 다음과 같은 정보가 필요하다.

 

1. 해당 인덱스의 숫자가,  앞의 숫자들에게 영향이 끼치는지?

->  예를들어, 3 3 5 6 과같은 숫자배열에서 5인숫자가 앞의 숫자들 3 에게 영향이 간다.

2. 해당 인덱스의 숫자가, 뒤의 숫자보다 작은지?

-> 예를들어 3 3 5 6 과 같은 숫자배열에서 5인 숫자는 앞의숫자 6보다 작다.

 

--> 1번을 해결하기위해 Stack이란 배열을 사용했다.

 

 

필자는  스택에 int[] 배열로  {해당 인덱스값, 인덱스} 로 스택에 넣었는데,

다른사람의 풀이를보니 인덱스만 넣어줘도 1번질문은 판별이 가능하다.

 

조건은 스택이 비어있지않고,  스택에 값이 해당숫자보다 작으면,  스택에서 꺼낸값을 업데이트한다.

 

문제를 보면 알겟지만, 이문제 특성상 맨 마지막값은 뒤에 있는 숫자가없으니 

마지막은 볼것도없이 -1 값을 넣고 빠져나와야한다.

 

마지막을 제외한,  해당숫자가 다음숫자보다 적은지를판단한다.

적으면, 값을 업데이트를해주고,

그 외의 경우들은 스택에 담아준다.

 

 

 

이렇게하면 스택에 고립되어있는 숫자들이 존재한다.

고립된 숫자들은 수가 너무큰 경우인데

고립된 숫자들은 모두 -1 로 반환하면된다. 

전체풀이

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<int[]> stack = new Stack<>();
        for(int i=0;i<numbers.length;i++){
            // 해당 숫자가 앞숫자에 영향이 가는지
            while(true){
               if(!stack.isEmpty()&&stack.peek()[0]<numbers[i]){
                   int[] p=stack.pop();
                   answer[p[1]]=numbers[i];
               }else{
                   break;
               }
            }
            //마지막이면 리턴
            if(i==numbers.length-1){
                answer[i]=-1;
                break;
            }
            //해당 숫자가 뒷큰수인지
            if(numbers[i]>=numbers[i+1]){
                stack.add(new int[]{numbers[i],i});
            }else{
                answer[i]=numbers[i+1];
            }
        }
        
        //아직도 못나온 스택값들은 전부 -1
        while(!stack.isEmpty()){
            int[] p= stack.pop();
            answer[p[1]]=-1;
        }
        return answer;
    }
}