💚[Lv.2] 뒤에 있는 큰 수 찾기

프로그래머스

 

시간복잡도도 생각하기

 

-시간 초과 코드

원인 : 이중for문 사용함

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        for(int i=0; i<numbers.length; i++){
            answer[i] = -1;
            for(int j = i+1; j<numbers.length; j++){
                if(numbers[i] < numbers[j]){
                    // 뒷 큰수가 있는 경우
                    answer[i] = numbers[j];
                    break;
                }
                
            }
        }
        
        
        return answer;
    }
}

 

 

-Stack 사용한 코드

이중 for문은 뒤에 있는 숫자들 매번 다 훑어보는거임

스택방법은 아직 답 못 찾은 숫자들만 대기줄에 세워두는 것

import java.util.*;

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

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

        for (int i = 0; i < n; i++) {
            // 현재 값이 스택 top보다 크면 → 뒷 큰 수 발견
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }

        return answer;
    }
}