뒤에 있는 큰 수 찾기

문제 설명

정수로 이루어진 배열 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]

---

입출력 예 설명

입출력 예 #1

2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.

입출력 예 #2

9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

스택을 이용해 풀 수 있다. 문제의 요구사항에 따라 자신보다 큰 가장 가까운 숫자를 찾기 위해, 우선 모든 숫자의 뒷 큰수를 -1로 설정해두고, 오른쪽부터 왼쪽으로 스택에 숫자를 넣어가며, 스택의 최상위 숫자보다 큰 숫자가 나올 경우 해당 숫자를 스택에서 빼고 그 자리에 뒷 큰수를 저장한다.

package LV2;

import java.util.Stack;

public class H154539 {
    public int[] solution(int[] numbers) {
        // numbers의 길이를 length에 저장한다.
        int length = numbers.length;

        // 결과를 담을 배열 answer를 초기화하고, 모든 원소를 -1로 설정한다.
        int[] answer = new int[length];

        // 숫자를 저장할 스택을 생성한다.
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < length; i++) {
            answer[i] = -1;
        }

        // 오른쪽에서 왼쪽으로 이동하면서 각 숫자에 대한 뒷 큰수를 찾는다.
        for(int i = length - 1; i >= 0; i--) {
            // 현재 숫자가 스택의 최상위 숫자보다 크면, 스택에서 숫자를 빼고 뒷 큰수를 현재 숫자로 설정한다.
            while(!stack.isEmpty() && stack.peek() <= numbers[i]) {
                stack.pop();
            }

            // 스택이 비어있지 않고, 스택의 최상위 숫자가 현재 숫자보다 크다면, 뒷 큰수를 스택의 최상위 숫자로 설정한다.
            if(!stack.isEmpty() && stack.peek() > numbers[i]) {
                answer[i] = stack.peek();
            }

            // 현재 숫자를 스택에 넣는다.
            stack.push(numbers[i]);
        }

        // 모든 숫자의 뒷 큰수를 담은 배열을 반환한다.
        return answer;
    }
}

answer 배열을 입력받은 numbers의 길이로 초기화하고, 모든 원소를 -1로 설정한다. 그 후, 스택을 생성한다.

그 다음, 오른쪽부터 왼쪽으로 숫자를 보면서, 현재 숫자가 스택의 최상위 숫자보다 클 경우, 스택에서 숫자를 빼고 해당 숫자의 뒷 큰수를 현재 숫자로 설정한다. 이 과정을 반복하여 모든 숫자에 대한 뒷 큰수를 찾는다. 마지막으로, 현재 숫자를 스택에 넣는다.

모든 숫자에 대해 이 과정을 반복하면, 최종적으로 모든 숫자의 뒷 큰수를 찾을 수 있다.