[Algorithm] Programmers_뒤에 있는 큰 수 찾기

💡 Programmers Lv2. 뒤에 있는 큰 수 찾기:

stack을 활용하여 뒤에 있는 큰 수로 갱신

🌱 코드 in Java

알고리즘: Stack

import java.util.*;

class Solution {
    public int solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Arrays.fill(answer, -1);
        Stack<Integer> idx = new Stack<>(); // 갱신되지 않은 numbers의 인덱스를 저장할 스택
        
        for (int i = 0; i < numbers.length; i++) {
            while (!idx.empty() && numbers[idx.peek()] < numbers[i])
                answer[idx.pop()] = numbers[i];
            idx.push(i);
        }
        return answer;
   }
}

이 문제는 사실 접근법이 잘 떠오르지 않아 힌트를 먼저 보고 시작했다. 어떤 자료구조를 사용해야 하지?하면서 스택?으로는 못 풀것 같은데? 했는데 스택이었다. 찾아보니 다른 사람들은가장 가까이에 있는 수라는 문장에서 스택을 떠올렸다고 한다. 내가 처음에 스택으로 못풀겠다 싶었던 건, 이미 지나간 원소에 대해 바로 뒷수는 나보다 작지만 저~~~ 뒤에 있는 수가 크면 어떻게 여기로 돌아오지? 라는 부분을 못풀어서였다. 쩝.

근데 다시 생각해보니 그래서 스택이었다. 갱신하지 못한 애들의 index를 스택에 넣어놓고, numbers[i]랑 numbers[idx.peek()]와 비교하면 되는거여따.. 진짜 이런 로지컬함이 내게도 바로바로 좀 떠올랐음 좋겠다.. ㅠ

🧠 기억하자

1. stack.pop()
   자바의 pop은 해당 원소를 반환해준다. C++이었나 어떤 언어가 반환을 안해줬던 기억이 있는데, 암튼 자바는 해줌!