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

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

프로그래머스

[문제]

 정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.

정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

 

[제한사항]

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

 

[코드]

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack=new Stack<>(); // numbers의 인덱스 저장
        stack.push(0);
        
        for(int i=1;i<numbers.length;i++) {
            // 스택의 제일 위에 있는 값 보다 현재 값이 더 크면 바로 뒤에 있는 큰 수 
            while(!stack.isEmpty()&&numbers[stack.peek()]<numbers[i]) {
                answer[stack.pop()]=numbers[i];
            }
            
            stack.push(i);
        }
        
        // 자신보다 큰 수가 뒤에 없어 스택에 남아있는 값들 -1 저장
        while(!stack.isEmpty())
            answer[stack.pop()]=-1;
        
        return answer;
    }
}

 

[고찰]

 처음에 2중 for문으로 풀었지만 시간 초과로 오답 처리를 받았다. 방법이 떠오르지 않아 다른 사람의 풀이방법을 참고하였더니 stack을 사용하는 문제였다. stack을 사용하면 단일 for문으로 해결할 있는데 스택의 제일 위에 있는 값과 numbers를 비교하면서 큰 값이 나오면 stack의 값을 계속 뽑아내는 방식이었다.