[프로그래머스] Lv 2. 뒤에 있는 큰 수 찾기 (Java)

출처: 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

입출력 예

---

풀이

자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이에 있는 숫자를 찾는 것이기 때문에 Stack을 사용하였습니다. (사실 어떻게 풀어야 하는지 막막해서 질문하기를 보니까 스택을 사용하는 문제라고 힌트를 얻었습니다..! 풀고 나서 생각해보니까 가장 가까이에 있는 숫자를 찾기 때문이라는 것을 알았습니다.)

 

자신보다 뒤에 있는 숫자 중 자신보다 큰 숫자를 찾아야 하기 때문에 배열을 뒤에서부터 돌아야 합니다.

스택에는 numbers 배열의 숫자들이 들어가는데 스택의 최상단에 있는 숫자는 자신보다 뒤에 있는 숫자 중 가장 가까이 있는 숫자일 것입니다.

만약 최상단의 숫자가 자신보다 크다면 그 숫자가 구하고자 하는 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이에 있는 숫자가 됩니다. 최상단의 숫자가 자신보다 작거나 같다면 필요없는 숫자이기 때문에 버려줍니다.

 

스택을 다 살펴봤는데 자신보다 큰 숫자가 없다면 스택이 비게 되는데 그 때는 -1을 담으면 됩니다.

 

스택을 살펴볼 때 종료되는 조건은 1) 스택을 전부 살펴봤을 때, 2) 최상단의 숫자가 자신보다 클 때입니다. 이때는 원하는 값을 구했으니 다음 숫자를 위해 자기 자신 또한 스택에 넣어줘야 합니다.

---

소스코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        Stack<Integer> s = new Stack<>();
        
        for(int i=numbers.length - 1; i>=0; i--){
            while(true){
                if(s.isEmpty()){
                    answer[i] = -1;
                    s.push(numbers[i]);
                    break;
                }
                
                if(s.peek() <= numbers[i]){
                    s.pop();
                }
                else{
                    answer[i] = s.peek();
                    s.push(numbers[i]);
                    break;
                }
            }
        }
        
        
        return answer;
    }
    
}

---

마치며 ...

코테 문제를 풀 때 어려운 점이 문제를 보고 필요한 자료구조를 딱 떠올리는 것인데, 특히 스택을 떠올리기가 어려운 것 같다 .. 이번 문제를 풀고 "가장 가까이에 있는" or "짝지어" 를 보면 스택을 떠올려야 한다는 것을 알았다 !!

생각해보면 짝지어서 뭔갈 하는 것도(ex. 괄호) 가장 가까이에 있는 자기자신 or 유사(짝)을 찾아서 연산하는 방식이다.

다음에 문제 풀 때도 비슷한 유형을 보면 꼭 스택을 사용해서 풀어야지 ..!!!! 😗