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

문제

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

 

---

접근

한줄 요약 : stack에 순서대로 값을 넣으면서 stack.peek보다 큰값이 들어오면 기존 stack에 있는 값들을 빼면서 업데이트 시킴

 

9,1,5,3,6,2라는 예제를 예로들자면

일단 스택이 비어있을땐 그대로 [9,0]을 넣어준다 (0은 순서를 나타내기 위한 index)

스택이 비어있지 않을 때는 두가지 분기로 나뉨.

1. stack.peek보다 작거나 같은 값이냐
2. stack.peek보다 큰 값이냐

1번의 경우 가장 뒤에서 가장 가까운 값을 못찾은 경우이고,

2번의 경우 가장 가까운 뒤의 값을 찾은 것.

 

1을 넣을때는 9보다 작으므로 [1,1]을 넣음

 

5를 넣을때는 stack.peek인 1보다 크므로

[1,1]을 스택에서 빼내고

answer[1(스택에 기록해둔 index)]을 현재값인 5로 할당

answer[1] = 5;

그다음 [5,2]를 스택에 넣음.

 

3을 넣을때는 5(stack.peek)보다 작으므로 [3,3]을 넣음

 

6을 넣을때는 stack.peek인 3보다 크므로

[3,3]을 스택에서 빼내고 answer[3]을 현재값인 6으로 할당

근데 스택을 또 확인해보니 stack.peek인 5보다 현재값인 6이 크므로

[5,2]를 스택에서 빼내고 answer[2]를 현재값인 6으로 할당

그 후 스택peek는 [9,0]이므로 더이상 못빼냄

그다음 [6,4]를 넣음

 

이러한 과정을 거치다보면 9처럼 끝날때까지 할당을 못하는 값이 있는데, 이러한 값을 처리하기위해 사전에 정답 배열을 -1로 초기화 시켜둠.

---

코드

function solution(numbers) {
    let answer = new Array(numbers.length).fill(-1);
    const stack = [];
    for(let i=0; i<numbers.length; i++){
        if(stack.length === 0){
            stack.push([numbers[i],i]);
        }
        else{
            if(stack[stack.length-1][0] >= numbers[i]){
                stack.push([numbers[i],i]);
            }
            else{
                while(stack.length != 0){
                    if(stack[stack.length-1][0] >= numbers[i]) break;
                    const [value, index] = stack.pop();
                    answer[index] = numbers[i];
                }
                stack.push([numbers[i],i]);
            }
        }
    }
    return answer;
}

import java.util.*;
class Element{
    int value;
    int index;
    public Element(int value,int index){
        this.value = value;
        this.index = index;
    }
}
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Arrays.fill(answer,-1);
        Stack<Element> stack = new Stack<>();
        for(int i=0; i<numbers.length; i++){
            if(stack.size() == 0){
                stack.push(new Element(numbers[i],i));
            }
            else{
                if(stack.peek().value >= numbers[i]){
                    stack.push(new Element(numbers[i],i));
                }
                else{
                    while(stack.size() != 0){
                        if(stack.peek().value >= numbers[i]) break;
                        Element temp = stack.pop();
                        answer[temp.index] = numbers[i];
                    }
                    stack.push(new Element(numbers[i],i));
                }
            }
        }
        return answer;
    }
}

---

주의

x