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

작성일: 2024-11-14

플랫폼 : https://school.programmers.co.kr/learn/challenges

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154539

접근 방식

현재의 인덱스의 값보다 큰 값을, 현재 인덱스 뒤에서 찾아야 한다. (없으면 -1)

주어진 배열의 최대 길이가 백만이기에, 완전탐색을 통해 2중 for문을 사용하면 시간복잡도가 O(n^2)이기에 시간 초과가 발생한다.

따라서, 완전탐색이 아닌 다른 방식을 이용해야 한다.

결과

소스 코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Arrays.fill(answer, -1); // 기본값 -1로 초기화

        Stack<Integer> stack = new Stack<>(); // 인덱스를 저장하는 스택

        for (int i = 0; i < numbers.length; i++) {
            // 현재 숫자가 스택의 맨 위 인덱스에 해당하는 숫자보다 크다면
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                int idx = stack.pop(); // 스택에서 인덱스를 꺼냄
                answer[idx] = numbers[i]; // 꺼낸 인덱스의 결과값 갱신
            }
            stack.push(i); // 현재 인덱스를 스택에 추가
        }

        return answer;
    }
}

stack 자료구조를 이용해서 연산을 했다. 시간복잡도 O(N) 이기에

느낀 점