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

문제 링크

뒤에 있는 큰 수 찾기

풀이

처음에는 다음과 같이 풀었다.

• 앞에서부터 탐색하면서 '가장 가까운 큰 수'를 탐색
• 만나면 해당 시작점의 인덱스에 맞게 값을 삽입
• 시간복잡도 예상 O(n^2)
• 시간 초과

다음으로 푼 방법은 다음과 같다.

• 배열을 다음과 같이 반복문을 돌리면서 진행한다.
  • 스택이 비어있지 않다면 stack의 가장 맨 위의 수와 현재 현재 수를 비교한다.
  • 만약 스택의 맨 위의 수가 현재 수 보다 작다면, 해당 스택의 맨 위의 수에 해당되는 인덱스에 현재 수를 넣는다. 이 로직은 스택의 맨 위의 수가 현재 수 보다 크게 되기 전까지 반복한다.
  • 현재 수를 스택에 넣는다.

말로 표현하니 로직이 생각보다 복잡해보인다.

코드는 다음과 같이 표기한다.

import java.util.Arrays;
import java.util.Stack;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];

        Arrays.fill(answer, -1); // -1로 모든 배열의 수를 초기화

        Stack<int[]> stack = new Stack<>(); // 스택에는 현재 수의 인덱스 - 현재 수를 배열로 만들어 넣는다.
        for (int i = 0; i < numbers.length; i++) {
            int number = numbers[i];
            while (!stack.isEmpty()) {
                if (stack.peek()[1] < number) {
                    answer[stack.pop()[0]] = number;
                } else break;
            }
            stack.push(new int[]{i, number});
        }

        return answer;
    }
}