[JAVA]뒤에 있는 큰 수 찾기(Programmers)

문제

◾문제 설명

 정수로 이루어진 배열 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,000,000이므로 $O(N^2)$으로는 풀 수 없다. 방법을 궁리하다가 감이 안와서 질문하기를 조회했다. 그 중, 이 문제를 참조하라고 했다.
 스택과 큐를 사용하여 푸는 문제인데, 나는 브루트포스로 풀었었다.
 스택을 사용하여 푸는 방법은 다음과 같다.

1. 초기값 인덱스인 0을 스택에 삽입한다
2. 반복문을 통해 스택의 peek와 현재 인덱스 값을 비교한다.
   1. 스택의 peek인덱스에 해당하는 값보다 현재 인덱스에 해당하는 값이 더 크다면 pop하여 해당 인덱스에 현재 인덱스에 해당하는 값 부여
   2. 스택에 현재 인덱스 push
3. 스택이 empty될때까지 pop하여 -1 값 할당

 

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        Stack<Integer> stk = new Stack<>(); // 인덱스를 담을 스택
        int[] answer = new int[numbers.length]; // 반환값
        int idx = 0;
        stk.push(idx);  // 인덱스 0 삽입
        // 반환값 갱신 반복문
        for(int i = 1; i < numbers.length; i++){
            // 스택의 peek값보다 현재값이 크다면, peek인덱스에 해당하는 값 갱신
            while(!stk.isEmpty() && numbers[stk.peek()] < numbers[i]){
                answer[stk.pop()] = numbers[i];
            }
            // 스택에 현재값 인덱스 삽입
            stk.push(i);
        }
        // 스택에 남아있는 인덱스 -1로 값 지정
        while(!stk.isEmpty()){
            answer[stk.pop()] = -1;
        }
        return answer;
    }
}

◾고찰

 탐색을 하는데에 있어서, 자료구조를 이용하면 다양한 탐색 방법이 가능하다. 이와 유사한 유형들이 있으니 잘 기억해뒀다가 활용할 수 있도록 체화해야겠다는 생각이 들었다.