프로그래머스 뒤에 있는 큰 수 찾기

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

프로그래머스

풀이

처음엔 2중 for문으로 풀었으나 테케 20번 부터인가 터져서 시간초과로 인해 통과하지 못했다..

1 <= numbers의 길이 <= 1,000,000 이니 당연한듯

 

감이 잘 오지 않아 검색해보았더니 index를 값으로 활용하여 stack을 가지고 푸는 문제였다.

 

while 문 안에 있는 조건은

스택에 값이 있으면서 && 가장 맨 위의 인덱스의 값이 현재 넣고자 하는 인덱스의 값 보다 작으면

해당 스택에 있는 값의 인덱스에 넣고자 하는 값(=뒷 큰수)을 넣도록 하는 것이다.

 

말로 풀어 쓰니 어렵지만 stack 은 index로 관리하고,

모든 i 는 다 stack에 들어가지만 스택에 있는 값의 뒷 큰수를 while 문 돌며 발견하게 되면 pop 해서 해당 인덱스에 현재 값을 넣으면 된다.

 

따라서 뒷 큰수를 발견하면 stack에서 빼주고 stack 에 남아있는 값들은 -1이 들어가는 값들이다.

어렵당.

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        
        Stack<Integer> stack = new Stack<>();
        
        int len = numbers.length;
        
        int[] answer = new int[len];
        
        Arrays.fill(answer, -1);
        
        for(int i = 0; i < len; i ++) {
            while(!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }
        
        return answer;
    }
}

https://leeprogramer.tistory.com/57

[프로그래머스] - 뒤에 있는 큰 수 찾기(LV2) java

해당 블로그 참고하였습니다.