LV2 뒤에 있는 큰 수 찾기 (Java)

 

---

 

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/154539#

프로그래머스

 

풀이

스택을 활용하여 풀 수 있는 문제였다.

 

처음에는 값 그 자체를 스택에 넣고, 큰 값이 오면 갱신해줘야했나? 했는데 이럴 경우 정답배열의 어떤 위치에 값을 업데이트 해줘야할 지 애매모호했다.

 

관점을 조금 바꿔서 인덱스를 넣는 방식으로 구현하면 풀 수 있었다. (스택에는 배열의 인덱스를 넣고, 값을 찾을땐 numbers[idx] 이런 방식으로 접근했다.)

 

 

문제 같은 경우에는 numbers 배열을 돌면서 스택을 관리해주고 처리하면 풀 수 있는데

 

스택을 처리할 때 두가지의 경우가 있다.

 

1. 스택이 비어있거나, 새로운 값(numbers에서 가져온 값)이 스택 가장 위에 값보다 클 경우

 

위 경우에는 그냥 스택에 쌓아주기만 하면 된다.

 

 

2. 새로운 값이 스택의 최상위 값보다 클 경우

 

새로운 값이 더 클 경우에는 스택 최상위값을 빼주고 (pop) , 정답배열의 해당 인덱스에 새로운값을 갱신해주면 된다. 그리고 이 과정을 스택이 비어있거나, 아니면 새로운 값보다 큰 값이 스택 최상위로 올 때 까지 반복해주면 된다.

 

만약 스택에 (값 기준으로) [5, 3, 2] 순으로 쌓여있고 (왼쪽이 가장 하단, 오른쪽이 상단), 새로운 값이 6이라고 가정했을 경우에 스택에 들어있는 값의 "뒤에 있는 큰 수" 는 모두 6이 된다.

 

그렇게 처리를 다 하면 새로운 값도 스택에 넣어주면 된다.

 

 

위 2상황으로 분기처리를 한다음 스택에 남아 있는 인덱스들은 모두 -1로 처리해주면 된다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int len = numbers.length;
        int[] answer = new int[len];
        Stack<Integer> st = new Stack<>();
        
        for(int i=0; i<len; i++){
            int newVal = numbers[i];
            // 비어있거나, 최상위 값이 새로운 값보다 클 때
            if(st.empty() || numbers[st.peek()] >= newVal){
                st.push(i);
                continue;
            }
            
            // 새로운 값이 더 큰 경우
            while(!st.empty() && numbers[st.peek()] < newVal){
                answer[st.pop()] = newVal;
            }
            st.push(i);
        }
        
        while(!st.empty()){
            answer[st.pop()] = -1;
        }
        
        return answer;
    }
}

 

후기

 

이런 문제를 보면 dp인가 싶다가도 스택인 경우가 많더라.