프로그래머스 뒤에 있는 큰 수 찾기 자바 풀이

문제 링크

문제 요약

정수 배열 numbers가 주어진다
각 원소에 대해 자신보다 뒤에 있으면서 더 큰 값 중 가장 가까운 수를 찾는다
그런 수가 없으면 -1을 담는다

문제 풀이

처음에는 각 원소마다 자신보다 뒤에 있는 원소들을 순서대로 훑으면서 처음 만나는 더 큰 값을 찾으면 되겠다고 생각했다.

하지만 이 방식은 비효율적이다.

numbers의 길이가 최대 1,000,000인데, 원소마다 뒤쪽을 전부 훑으면 최악의 경우 비교 횟수가 10^12에 가까워진다.

이 문제의 핵심은 뒤에서부터가 아니라 앞에서부터 순서대로 처리하면서, 아직 뒷 큰수를 못 찾은 인덱스만 스택에 남겨둔다는 점이다.

스택에는 아직 자신보다 큰 수를 찾지 못한 원소들의 인덱스를 넣어둔다.

새로운 원소를 만나면, 스택 맨 위에 있는 인덱스의 값이 새 원소보다 작을 동안 계속 꺼내면서 그 인덱스의 답을 새 원소로 채운다.

이렇게 하면 스택에 남아 있는 인덱스는 항상 아직 뒷 큰수를 못 찾은 원소들만 남는다.

각 인덱스는 스택에 한 번 들어가고 한 번만 빠지기 때문에 전체 시간 복잡도는 O(n)이다.

최종 코드

java

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int n = numbers.length;
        int[] answer = new int[n];
        Arrays.fill(answer, -1); // 뒷 큰수가 없는 경우 기본값은 -1
        
        Deque<Integer> stack = new ArrayDeque<>(); // 아직 뒷 큰수를 못 찾은 인덱스들을 담아둔다
        
        for(int i=0;i<n;i++){
            // 스택 맨 위 인덱스의 값보다 현재 값이 크면, 그 인덱스의 뒷 큰수를 찾은 것
            while(!stack.isEmpty() && numbers[stack.peek()] < numbers[i]){
                answer[stack.pop()] = numbers[i];
            }
            
            stack.push(i); // 아직 뒷 큰수를 못 찾았으므로 인덱스를 스택에 보관
        }
        
        return answer;
    }
}

뒤에 있는 큰 수 찾기

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기