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

문제

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

제한사항
4 ≤ numbers의 길이 ≤ 1,000,000
1 ≤ numbers[i] ≤ 1,000,000

입출력 예

numbers	result
[2, 3, 3, 5]	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

문제 출처

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

생각

• 제한사항의 numbers의 길이와 원소의 크기가 범상치 않다,,, 시간 초과에 유의해야겠다 😵‍💫
• 원소가 현재 처리 중인 인덱스를 담을 stack을 생성하자
• 현재 뒷큰수를 알고자 하는 수 numbers[stack.peek()] 보다 numbers[i] 가 더 크면 정답 배열에 stack.peek() 번째 위치에 numbers[i] 값을 넣고, stack에서 처리된 인덱스 값을 제거

answer[stack.peek()] = numbers[i];
stack.pop();

answer[stack.pop()] = numbers[i];

코드

import java.util.*;

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

다른 사람의 풀이

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Arrays.fill(answer, -1);
        Stack<Integer> s = new Stack<>();
        s.push(0);
        for(int i = 1; i < numbers.length; i++){
            while(!s.isEmpty()){
                int idx = s.pop();
                if(numbers[i] > numbers[idx]){ // 뒤가 더 클때
                    answer[idx] = numbers[i];
                } else { // 앞이 더 크거나 같을 때
                    s.push(idx);
                    break;
                } 
            }
            s.push(i);
        }

        return answer;
    }
}

• 배열 초기화 할 때 Arrays.fill()을 사용할 수 있구나,,
• stack을 뒷큰수를 확인할 현재 숫자의 index 보관 상자로 사용한 점은 동일했다 ≧(´▽｀)≦