[프로그래머스] Lv.2 - 뒤에 있는 큰 수 찾기 - JAVA

문제

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

 

 

제한사항

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

 

 

입출력 예시

 

 

풀이

처음에 뒤에 있는 수를 반복하여 처음 큰 수가 나올 때까지 찾고 break하는 while문을 통해서 풀이했는데,

20, 21, 22, 23번에서 시간 초과 오류가 발생했다.

이에 따라 해결법을 찾아보다가 stack을 통한 풀이를 보고 풀이했다.

숫자 배열을 1부터 끝까지 반복하면서 stack에 있는 수가 현재 배열의 i번째 수보다 작으면 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;
    }
}

 

 

문의사항이나 피드백은 댓글로 남겨주세요.