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

링크

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

프로그래머스

 

설명

1. 이중 반복문으로 체크하는 숫자 중에 제일 먼저 만나는 수를 저장했지만 시간초과로 실패

 

2. 1은 이중 반복문이기 때문에 O(n^2) 이지만 스택에 index 를 저장하는 형식으로 O(n)으로 풀도록 변경함

 

가장 stack의 최상위에 올라와 있는 숫자와 가장 최근의 숫자 보다 큰 숫자가 나온다면,

해당 숫자보다 작은 숫자들에 큰 숫자를 모두 적용한다.

 

Ex. ) [9, 5, 4, 3, 2, 1, 6, 1, 1] 이라면

index : 0, 숫자 : 9 -> index:5, 숫자 1 까지 모두 stack에 push 

 

index : 6, 숫자 6에 도착했을 때

1 과 6을 비교하여 큰 숫자를 발견, 

9를 제외한 숫자까지 모두 pop 하고 index : 1 ~ index : 5까지는 모두 6을 대입한다.

 

이런 식으로 마지막까지 반복문을 적용하면 된다.

 

풀이

 

실패 코드

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        // 그리디
        for (int i=0; i<numbers.length-1; i++) {
            int currentNumber = numbers[i];
            int backBigNumber = Integer.MAX_VALUE;
            for (int j=i+1; j<numbers.length; j++) {
                int backNumber = numbers[j];
                if (currentNumber < backNumber) {
                    backBigNumber = backNumber;
                    break;
                }
            }
            answer[i] = backBigNumber == Integer.MAX_VALUE ? -1 : backBigNumber;
        }
        
        // 가장 뒤 숫자는 뒷 숫자가 없기 때문에 -1
        answer[numbers.length-1] = -1;
        
        return answer;
    }
}

 

성공 코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        for (int i=0; i<numbers.length; i++) {
            answer[i] = -1;
        }
        
        Stack<Integer> stack = new Stack<>();
        for (int i=0; i<numbers.length; i++) {
            int currentNumber = numbers[i];
            
            // 스택이 비어 있지 않고, 현재 숫자가 스택의 맨 위 인덱스의 숫자보다 클 때 현재의 숫자를 넣어준다.
            while(!stack.isEmpty() && numbers[stack.peek()] < currentNumber) {
                int idx = stack.pop();
                answer[idx] = currentNumber;
            }
            
            stack.push(i);
        }
        
        return answer;
    }
}