Lv.2 : 뒤에 있는 큰 수 찾기

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 현재 인덱스의 수보다 뒤에있는 수 중에서 현재 수보다 크면서 가장 가까운 수를 찾는다.
• 그런 수가 없다면 -1을 저장한다.

🔸 문제 풀이 🔸

• 현재 수보다 큰 '가장 가까운 수'는 스택을 이용해 찾을 수 있다.
• 뒤에서부터 앞으로 진행해서, 현재 수보다 큰 값이 나올 때 까지 스택에서 수를 빼낸다. 만약 없다면 -1을 저장하고 현재 값을 스택에 넣고 다음을 계산한다.
  • 현재 수보다 작은 수를 스택에서 빼도 되는 이유는 어차피 현재 수를 스택에 넣기 때문에, 이 다음 계산에서 생략해도 되기 때문이다.

---

🔸 코드 🔸

import java.util.Stack;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];

        Stack<Integer> stack = new Stack<>();

        for (int i = numbers.length-1; i >= 0; i--) {
            answer[i] = -1;

            while(!stack.isEmpty()  && stack.peek() <= numbers[i])
                stack.pop();

            if (!stack.isEmpty())
                answer[i] = stack.peek();

            stack.push(numbers[i]);
        }

        return answer;
    }
}

🔸 코드 해석 🔸

• 주어진 배열 numbers를 뒤에서부터 앞으로 탐색하며 계산한다.
  • 뒤에 있는 큰 수가 없을 수 도 있으므로, answer[i]를 -1로 초기화 한다.
  • 스택이 비거나 현재 값보다 큰 수가 나올 때 까지 원소를 꺼낸다.
  • 만약 스택에 원소가 있다면, 그 수가 현재 수보다 큰 뒤에있는 수 이므로 answer[i]에 저장한다.
  • 현재 수를 스택에 넣고 다음 계산을 진행한다.

---

🔸 end 🔸

• 처음엔 2중 반복문으로 구현해서, 다음 수를 직접 선형적으로 탐색하는 방법을 썼는데, 테스트 후반 부분에서 시간초과가 났다.
• dp인가 했지만 직전에 풀이한 문제의 다른 사람들 풀이에서 이 문제가 언급되어서 스택을 적용해보고자 했고, 쉽게 풀이되었다. 자료구조를 알맞게 선택하는게 얼마나 중요한지 알 수 있었다.