프로그래머스 뒤에 있는 큰 수 찾기

문제

---

리뷰

처음에는 이중 for문을 이용해서 풀이를 했었다.

그런데 이렇게 하니 테스트 케이스 20번~23번에서 시간 초과가 떴다.

알고 보니 이 문제는 스택을 이용해서 풀어야 하는 문제였다.

코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
    	// 1.
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();
        
        // 2.
        for(int i = 0; i < numbers.length; i++){
        	// 3.
            while(stack.isEmpty() == false && numbers[stack.peek()] < numbers[i]){
            	// 4.
                answer[stack.pop()] = numbers[i];
            }
            // 5.
            stack.push(i);
        }
        7.
        while(!stack.isEmpty()){
            answer[stack.pop()] = -1;
        }
        8.
        return answer;
    }
}

1. numbers와 같은 크기의 배열 answer를 선언한다.
2. for문을 돌며 numbers의 0부터 마지막 인덱스까지 순환하는데
   • 스택에는 인덱스 i 보다 작은 인덱스 값들만 저장할 것이므로 조건문을 먼저 작성한다
   • 스택에는 배열의 요소 값을 저장하는게 아니라 인덱스 값을 저장함
3. while문을 이용하여 스택이 비어있지 않고,
   numbers[스택에 저장된 인덱스 값]가 numbers[i]보다 작으면
4. numbers와 같은 크기의 배열인 answer[스택에 저장된 인덱스 값]에 numbers[i]를 저장한다.
   • 예를 들어 i가 3이고 stack에서 pop이 한번도 이뤄지지 않았다면 스택에는 {2,1,0}이 들어 있을 것이다.
5. 현재 인덱스 i를 stack에 push한다.
6. 반목문을 빠져 나오고
7. 반복문에서 처리하지 못한 스택의 인덱스 값들은 더 큰 값이 없다는 말이므로 answer[각 인덱스]에 -1을 저장한다.
8. answer를 반환한다.