[Java] 숫자형 배열에서 다음 큰 수 찾는 방법

2023-03-23

---

사진: Unsplash 의 David Clode

---

1. 방법

 

스택을 사용하면 해결을 할 수 있다. 주어진 숫자형 배열의 인덱스를 스택에 저장하고 각 인덱스 마다 비교하여 다음 큰 수를 찾을 수 있다. 

 

    public int[] test(int[] numbers) {
        Stack<Integer> stack = new Stack<>();
        int[] answer = new int[numbers.length];

        for (int i = 0; i < numbers.length; i++) {
            //스택이 비어있지 않고 스택에 number[스택최상단인덱스] <  number[인덱스]
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                // number[스택최상단인덱스] <  number[인덱스] -> 스택최상단인덱스의 다음 큰 수는 number[인덱스] 가 된다.
                answer[stack.pop()] = numbers[i]; 
            }
            //위의 경우가 아니면 인덱스 스택에 저장
            stack.push(i);
        }
        //루프 종료에도 스택에 남아 있다면 해당 인덱스들은 다음큰 수가 존재하지 않는다.
        while (!stack.isEmpty()) {
            answer[stack.pop()] = -1;
        }
        return answer;
    }

---

메인 이미지 출처 : 사진: Unsplash의David Clode