[프로그래머스] 뒤에 있는 큰 수 찾기(JAVA)

문제

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

---

풀이(40분)

import java.util.*;


class Solution {
    public int[] solution(int[] numbers) {
        Stack<Integer> stack = new Stack<>();
        int[] answer = new int[numbers.length];

        Arrays.fill(answer, -1);

        for (int i = 0; i < numbers.length; i++)
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }
        return answer;
    }
}

 

초기 뒤에 있는 것중 자기보다 큰 수 중 가장 작은 것을 찾는 문제인줄 알고 이분탐색으로 풀었으나 아니었고, 스택을 사용했다.

 

스택을 사용하면서 쓴 가장 중요한 아이디어는 일반적으로 스택에 값을 직접 넣지만 이번엔 인덱스를 넣는다는 것!

 

문제의 예시인 2 3 3 5로 입력이 들어왔을 때를 생각해보자.

 

1. 처음에 2가 들어온다. 스택이 비어있기 때문에 일단 넣는다. 이 때 값을 넣는 것이 아닌 인덱스인 0을 넣는다.

2. 3이 들어온다. 스택은 차있고, peek인덱스는 0이고, 값은 2다. 자기 자신은 3이고 인덱스는 1이다.

2-1. 2 < 3이 되므로 스택을 팝하고, 값을 numbers[i]인 3으로 넣어준다.

 

이 과정을 반복하면 된다.