[Lv2] 뒤에 있는 큰 수 찾기

📌 문제

 

뒤에 있는 큰 수 찾기 (스택)

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

프로그래머스

 

📌 풀이

• 이 문제는 우선 주어진 제한사항에 따라 이중 for 문이 아닌 다른 방법을 사용해서 정답을 탐색해야 함을 인지해야 합니다
• 각 자리 수 크기를 비교하기 위해 스택을 사용해야 시간 초과를 방지할 수 있습니다.
• 자세한 풀이는 코드의 주석으로 대체합니다.

 

📌 코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        
        //핵심 : 주어진 numbers의 길이가 백만이므로 이중 for문 사용 못함
        
        //stack 선언
        Stack<Integer> stack = new Stack<>();
        
        int[] answer = new int[numbers.length];
        
        //answer array는 값을 모두 -1로 초기화
        Arrays.fill(answer, -1);
        
        for(int i = 0; i < numbers.length; i++){
            
            //스택이 비어있지 않고 현재 스택의 인덱스에 해당하는 값이 다음 값보다 작다면(다음값이 크다면)
            while(!stack.isEmpty() && numbers[stack.peek()] < numbers[i]){
            	//answer 배열의 값을 해당 값으로 바꿔줍니다.
                answer[stack.pop()] = numbers[i];
            }
            
            //스택에 탐색이 필요한 인덱스 값을 넣는다.
            stack.push(i);
        }
        
        return answer;
    }
}