[pro] 프로그래머스 level2 154539 뒤에 있는 큰 수 찾기 (Java) - 스택

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

[풀이]

스택을 이용해 풀 수 있다.

예시2의 [9, 1, 5, 3, 6, 2] 에 대해서 하강곡선일 때는 스택에 해당 인덱스를 넣어준다. 9, 1의 인덱스 0,1을 스택에 넣으면, 그 다음 수인 5에 대해서는 1 5 로 상승곡선을 보인다. 이는 1보다 뒤에 있는 큰 수 중 가장 가까운 수가 5라는 것이므로 하강곡선에 한해서 stack.pop() 인덱스에 대한 정답 배열을 채워준다. 다시 9, 5, 3 까지는 하강곡선이므로 스택에 들어가 있을 것이고, 6에 대해서 3 6으로 상승 곡선을 그리게 된다. 따라서 answer[stack.pop()] = 6 (3에 대한 인덱스), answer[stack.pop()] = 6 (5에 대한 인덱스) 가 된다. 이후 9 6 2 의 하강곡선을 그리는 수들의 인덱스만 남게 될 것이다. 이 수들은 뒤에 더 큰 수가 없다는 것이므로 -1을 채워준다.

 

[코드]

 

package heal_stack_dequeue;
import java.util.*;

class Pro_level2_154539 {
    public int[] solution(int[] numbers) {
        int[] answer = {};
        //모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return
        
        int len = numbers.length;
        answer = new int[len];
        Stack<Integer> stack = new Stack<>();
        
        for(int i=0; i<len; i++){
            while(!stack.isEmpty() && numbers[stack.peek()] < numbers[i]){
                answer[stack.pop()] = numbers[i]; 
            }
            stack.push(i); //하강곡선일 때
        }
        
        while(!stack.isEmpty()){
            answer[stack.pop()] = -1;
        }
        
        return answer;
        
    }
}