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

---

💡 아이디어

"가장 가까이 있는 수"  이런 키워드가 나오는 문제들은 모두 Stack을 활용한 문제풀이를 고려해야 합니다.

가장 가까운, 연속된, 붙어있는, 괄호 2~단어를 찾아야 하는 문제가 모두 그 예시로 볼 수 있습니다.

 

 

📖 풀이과정

 

1. Stack을 int[]형으로 선언해 i번째 수와 인덱스 i를 집어넣을 수 있도록 만듭니다.

Stack<int[]> stack = new Stack<>();

 

2. 스택이 비어있는 상태라면 i번째 수와 i를 stack에 넣고, 다음 반복문을 실행합니다.

if(stack.isEmpty()){
	stack.push(new int[]{numbers[i],i});
}

3. 스택이 비어있지 않고 stack에 가장 위에 있는 수가 i번째 수보다 작을 때, stack에서 pop한 수의 인덱스에 현재 i번째 수를 저장합니다.

while(!stack.isEmpty() && (stack.peek())[0]<numbers[i]){
	answer[(stack.pop())[1]]=numbers[i];
}

 

4. stack에서 i번째 수보다 작은 수를 모두 꺼낸 뒤, stack에 i번째 수와 i를 넣고 다음 반복문을 실행합니다.

stack.push(new int[]{numbers[i],i});

 

5. numbers의 모든 숫자들을 확인하고 stack에 남아있는 수들은 모두 자신보다 뒤의 큰 숫자가 없는 것으로 모두 -1를 넣어줍니다.

---

전체 코드

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        Stack<int[]> stack = new Stack<>();
        for(int i=0;i<numbers.length;i++){
            if(stack.isEmpty()){//스택이 비어있으면 검사 필요 없이 넣어줌.
                stack.push(new int[]{numbers[i],i});continue;
            }
            //i번째 수보다 작은 수들 모두 빼내서 해당 index를 i번째 수로 채운다.
            while(!stack.isEmpty() && (stack.peek())[0]<numbers[i]){
                answer[(stack.pop())[1]]=numbers[i];
            }
            stack.push(new int[]{numbers[i],i});
        }
        for(int[] i:stack)//자신보다 뒤에 큰 수가 없는 수들은 모두 -1 넣어줌.
            answer[i[1]]=-1;
        
        return answer;
    }
}