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

📚 문제 설명

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항

• 4 ≤ numbers의 길이 ≤ 1,000,000
  1 ≤ numbers[i] ≤ 1,000,000

🔎 입출력 예

💻 처음으로 푼 코드

처음에는 간단한 문제라고 생각해 배열을 사용해서 풀었었다. 하지만 test 20번 부터 시간초과 발생...😥

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        int index = 0;
        while(index < numbers.length) {
            for(int i=index; i<numbers.length; i++) {
                if(numbers[index] < numbers[i]) {
                    answer[index] = numbers[i];
                    break;
                }
            }
            if(answer[index] == 0) answer[index] = -1;
            index++;
        }
        
        return answer;
    }
}

💻 최종 코드

import java.util.*;
class Solution {  //스택을 사용해서 풀어야하는 문제
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();
        
        stack.push(0); //첫번째 인덱스 값
        for(int i=1; i<numbers.length; i++) {
            while(!stack.empty() && numbers[stack.peek()] < numbers[i]) {
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i); //다음 인덱스 값을 넣어줌
        }
        
        // stack에 남은 인덱스 값들 = -1
        while(!stack.empty()) {
            answer[stack.pop()] = -1;
        }
        
        return answer;
    }
}

📖 Solution

스택으로 풀어야한다는 힌트를 얻고 고민을 해보았지만 잘 이해가 가지 않았다. 그래서 다른 분의 블로그를 보고 이해하며 다시 풀어보았다!

스택에 인덱스 값을 넣어 관리하는 방식으로 사용하였다.
현재 값이 스택에 최상단(stack.peek()) 값보다 크면 뒤에 있는 큰 수에 해당 한다.
이 경우에 하위 스택 원소들도 탐색해 보면서 추가로 해당하는 원소가 있는지 판별 후 있다면 pop 해주면서 인덱스에 정답 값을 넣어준다.

마지막으로 뒤에 있는 큰 수가 없는 케이스를 위해 스택이 남아있는 경우 -1로 채워준다.

참고 : https://sasca37.tistory.com/306 🙌🏻