[JAVA 문제 풀이] 338. 뒤에 있는 큰 수 찾기

내가 작성한 코드 1

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        List<Integer> origin = new ArrayList<>(); // 배열을 담을 리스트

        for (int n : numbers) {
            origin.add(n);
        }

        for (int i = 0; i < origin.size(); i++) {
            List<Integer> subList = origin.subList(i + 1, numbers.length); // 다음 인덱스부터 담은 리스트

            // 현재값이 찾아낸 값보다 클 때만 저장
            for (int j = 0; j < subList.size(); j++) {
                if (origin.get(i) < subList.get(j)) {
                    answer[i] = subList.get(j);
                    break;
                } else {
                    continue;
                }
            }

            // 0이면 자신보다 큰 값이 뒤에 없다는 뜻 >> -1로 저장
            if (answer[i] == 0) {
                answer[i] = -1;
            }
        }

        return answer;
    }
}

• 시간 초과로 폐기 >> 반복을 너무 많이 돔

내가 작성한 코드 2

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>(); // 인덱스를 저장하는 스택

        for (int i = 0; i < numbers.length; i++) {
            // 스택이 비어있지 않고, 현재 값이 스택 top 인덱스의 값보다 크면
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                answer[stack.pop()] = numbers[i]; // 정답에 현재 값 저장
            }
            stack.push(i); // 현재 인덱스를 스택에 저장
        }

        // 스택에 남아있는 인덱스는 오른쪽에 더 큰 수가 없음
        while (!stack.isEmpty()) {
            answer[stack.pop()] = -1;
        }

        return answer;
    }
}