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

프로그래머스 뒤에 있는 큰 수 찾기 바로가기

문제 설명

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

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

접근 방식

스택을 활용했다.

스택에는 [numbers[index], index] 값이 들어간다.

numbers 배열을 탐색하면서 스택의 top이 현재 원소보다 작다면 answer[index]에 현재 원소를 넣어주고 pop해준다. 스택에는 현재 원소를 push 해준다.

배열 탐색이 끝난 후 스택에 남아있는 원소들은 뒤 큰 수가 없다는 뜻이므로 해당하는 index에 -1을 넣어준다.

코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int leng = numbers.length;
        
        int[] answer = new int[leng];
        
        Stack<MyPair> stk = new Stack<>();
        
        stk.push(new MyPair(numbers[0], 0));
        
        for(int i = 1 ; i < leng; i++){
            
            while(!stk.isEmpty() && stk.peek().num < numbers[i]){
                answer[stk.peek().position] = numbers[i];
                stk.pop();
            }
            
            stk.push(new MyPair(numbers[i], i));
        }
        
        while(!stk.isEmpty()){
            answer[stk.pop().position] = -1;
        }
        
        return answer;
    }
    static class MyPair{
        int num, position;
        
        public MyPair(int num, int position){
            this.num = num;
            this.position = position;
        }

    }   
    
}

Disscussion