Programmers Lv.2 – JAVA 뒤의 큰 숫자 찾기

문제

정수 배열이 있습니다. 배열의 각 요소에 대해 다음 숫자 중 가장 크고 가장 가까운 숫자를 두 번째로 큰 숫자라고 합니다.

매개변수로 숫자의 정수 배열이 주어지면 solve 함수를 완성하여 모든 요소에 대한 마지막 큰 숫자를 순서대로 포함하는 배열을 반환합니다. 그러나 큰 수가 존재하지 않는 요소는 -1을 포함합니다.

설명

– 처음에는 중복 for 문으로 문제를 해결했지만 시간 초과로 인해 계속 지속되고 마지막 4개는 실패했습니다. 그래서 해결책을 찾았고 Stack으로 해결책을 찾았습니다.

문제는 단순히 2,3,3,5가 있으면 2의 경우 자기보다 큰 것이 3이고, 3은 5보다 크고 5가 없으므로 -1이라는 것이다.

결국 3, 5, 5, -1이 되는 구조이다.

스택으로 해결할 때도 마찬가지입니다. 값은 스택의 마지막 숫자부터 시작하여 스택으로 푸시되고 현재 인덱스가 스택에 저장된 값보다 크면 팝될 때까지 다음 값과 비교됩니다. 스택이 비게 될 때까지 비교하고 비어 있으면 -1이 입력된다. for 문은 numbers.length-1에서 0까지 실행되며 for 문이 반복되는 동안 모든 값을 스택에 푸시합니다.

import java.util.*;

class Solution {
    public int() solution(int() numbers) {
          int() answer = new int(numbers.length);
        Stack<Integer> s = new Stack<>();
      
        for(int i=numbers.length-1; i>=0; i--){
            while(!s.isEmpty()){
                if(s.peek() > numbers(i)){
                    answer(i) = s.peek();
                    break;
                }else{
                    s.pop();
                }
            }
            if(s.isEmpty()){
                answer(i) = -1;
            }
            s.push(numbers(i));
        }
        return answer;
 
    }
}