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

 

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] result = new int[numbers.length]; // 결과를 저장할 배열
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < numbers.length; i++) {
            // 스택이 비어있지 않고, 현재 숫자가 스택의 top에 있는 인덱스의 숫자보다 큰 경우
            while (!stack.isEmpty() && numbers[i] > numbers[stack.peek()]) {
                result[stack.pop()] = numbers[i]; // 뒷 큰수를 결과 배열에 저장
            }
            stack.push(i); // 현재 인덱스를 스택에 push
        }
        
        // 스택에 남아있는 인덱스는 뒷 큰수를 찾지 못한 원소들이므로 -1로 설정
        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }
        
        return result;
    }
    public static void main(String[] args) {
        int[] numbers = {9, 1, 5, 3, 6, 2};
        Solution sol = new Solution();
        int[] result = sol.solution(numbers);
        System.out.println(Arrays.toString(result));
        
    }
}

와... 경이롭다.

내가 짠 코드는 바로 시간 초과가 나버렸다.

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] result = new int[numbers.length]; // 결과를 저장할 배열 초기화
        
        for (int i = 0; i < numbers.length; i++) {
            result[i] = -1; // 기본값으로 -1 설정
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] < numbers[j]) {
                    result[i] = numbers[j]; // 자신보다 큰 첫 번째 수를 찾으면 저장
                    break; // 더 이상의 탐색은 필요 없으므로 반복문 탈출
                }
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] numbers = {9, 1, 5, 3, 6, 2};
        Solution sol = new Solution();
        int[] result = sol.solution(numbers);
        System.out.println(Arrays.toString(result));
        
    }
}