프로그래머스 Lv.2 뒤에 있는 큰 수 찾기-JAVA

 

문제

정수로 이루어진 배열 numbers가 있습니다. 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷큰수라고 합니다.

정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return하도록 solution함수를 완성해주세요. 단, 뒨 큰수가 존재하지 않는 원소는 -1을 담습니다.

 

 

 

풀이

- 처음에 문제를 2중 for문으로 풀었는데 시간초과로 계속 통과하다 마지막 4개를 통과못했다. 그래서 풀이를 찾아봤고 풀이는 stack을 사용하여 풀었다.

문제는 간단하게 2,3,3,5 가 있을 경우 2의 경우 자신보다 크면서 가장 가까운게 3이고, 3은 5가 크고 5는 없으니 -1이다

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

 

Stack으로 풀 때도 마찬가지이다. stack에 맨 뒷자리부터 값을 stack에 넣고 현재 인덱스가 stack에 담긴 값보다 크면 pop을 통해 다음 값이랑 비교를 해나간다. 그렇게 stack이 빌떄까지 비교하다가 비게 된다면 -1을 넣는다. for문은 numbers.length-1 부터 0까지 하고 for문을 돌면서 모든 값을 stack에 넣으면 된다.

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;
 
    }
}