뒤에 있는 큰 수 찾기(Java)

bearMin·2024년 2월 6일

🎯문제

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

✏️풀이

코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        // answer 배열의 모든 값을 -1로 채움
        Arrays.fill(answer, -1);
        
        // stack 생성
        Stack<Integer> stack = new Stack<>();
        
        // 맨 뒤에 있는 값부터 배열의 길이만큼 반복
        for(int i = numbers.length - 1; i >= 0; i--) {
        	// stack이 비어있지 않으면서
            // stack 맨 위의 값이 numbers[i]보다 작거나 같다면
            while(!stack.isEmpty() && numbers[i] >= stack.peek()) {
            	// stack에서 값을 제거
                stack.pop();
            }
            
            // 만약 stack이 비어있지 않다면
            if(!stack.isEmpty()) {
            	// 가장 위에 있는 값을 저장
                answer[i] = stack.peek();
            }
            
            // stack에 값을 넣어줌
            stack.push(numbers[i]);
        }
        
        return answer;
    }
}

설명

자료구조 중 스택을 사용하여 문제를 풀었다. 스택은 맨 처음 들어온 값이 가장 마지막에 나가는 FILO(First Input Last Output, 선입후출) 구조이다.

맨 처음 answer의 모든 값을 -1로 채워준다. 이유는 뒤에 있는 큰 수가 없다면 -1을 입력해줘야하기 때문에, 이후에 값을 입력하기 편하도록 -1로 초깃값을 설정한 것이다.

먼저 전체적인 흐름을 얘기해보자면, 스택을 생성한 뒤에 스택이 비어있지 않으면서 numbers[i]에 있는 값보다 작거나 같은 경우에는 스택에서 값을 제거해준다. 위의 조건을 while문을 통해 계속 반복해준다. 반복이 끝난 뒤에 스택이 비어있지 않다면 가장 위에 있는 값을 answer[i]에 넣어준다. 그리고 스택에 numbers[i]의 값을 넣어준 뒤 i를 하나 감소 시켜서 반복을 계속 한다.

위의 흐름을 통해 문제가 해결이 되는 이유는 맨 뒤의 인덱스부터 탐색을 진행하기 때문이다. 현재 자신보다 뒤에 있는 수 중 크면서 자신과 가장 가까운 수를 answer 배열에 저장해야한다. 이때 뒤에서부터 스택에 값들을 저장한다면 자신과 가장 가까운 수를 먼저 탐색할 수 있게 되는 것이다.

왜냐? 스택은 FILO이기 때문에!

해당 과정을 예를 들어 설명해보자면

numbers	answer
[3, 2, 3, 5]	[5, 3, 5, -1]

이라는 값이 있을 때, 우리는 맨 뒤에서부터 탐색을 진행할 것이다.
이때 이미 answer에는 [-1, -1, -1, -1]로 초기화가 되어있을 것이다.

맨 뒤인 5를 가지고 탐색할 때,
스택 = [], answer = [-1, -1, -1, -1]이다.
스택이 비어있기 때문에, while문과 if문을 넘어가고 스택에 5를 저장한다.

그다음 3을 가지고 탐색한다.
스택 = [5], answer = [-1, -1, -1, -1]이다.
스택이 비어있지 않으나, numbers[i] = 3이 5보다 작기 때문에 while문을 넘어가고 if문을 실행한다. answer[i] = 5를 넣고, 스택에 3을 저장한다.

그다음 2을 가지고 탐색한다.
스택 = [3, 5], answer = [-1, -1, 5, -1]이다.
스택이 비어있지 않으나, numbers[i] = 2가 3보다 작기 때문에 while문을 넘어가고 if문을 실행한다. answer[i] = 3을 넣고, 스택에 2를 저장한다.

그다음 3을 가지고 탐색한다.
스택 = [2, 3, 5], answer = [-1, 3, 5, -1]이다.
스택이 비어있지 않으나, numbers[i] = 3이 2보다 크기 때문에 스택에서 2를 제거한다. 이후 다시 while문을 진행해보면 numbers[i] = 3이 3과 같기 때문에 역시 제거한다. 그리고 다시 진행을 했을 때, 5가 3보다 크기 때문에 반복문을 빠져나오고 if문을 실행한다. answer[i] = 5를 넣고, 스택에 3을 저장한다.

모든 탐색을 마친 뒤에 answer는 [5, 3, 5, -1] 이 된다.

이처럼 스택에는 현재 위치의 바로 뒤의 값과 그보다 큰 수만 저장이 된다. 현재 위치의 바로 뒤의 숫자보다 작은 수들은 저장이 되지 않는 것이다!

현재 위치의 값이 바로 뒤의 값보다 작을 경우 배열에는 바로 뒤의 값이 저장이 되고, 바로 뒤의 값보다 클 경우 바로 뒤의 값보다 작은 값들이랑은 비교할 필요없이 더 큰 값들과 비교하게 되는 것이다.

이러한 방식을 사용해서 배열에 값들을 저장한 뒤 반환해주어 해결하였다.