[Algorithm_Java] 뒤에 있는 큰 수 찾기 (Success)

프로그래머스

 

☕Language: Java

 

🚨 시간 초과 실패

- Brute Force로 시도했지만, 두 번째 반복문에서 크기를 줄였지만 시간 초과

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        for(int i=0; i<numbers.length; i++){
            answer[i] = -1;
 
            for(int j=i+1; j<numbers.length; j++){                
                if(numbers[i]<numbers[j]){
                    answer[i] = numbers[j];
                    break;
                }
            }
        }
        return answer;
    }
}
 

 

😮 찾아본 풀이

Stack 활용

 

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

1. Stack<Integer> reverseNumbers

    - 큰 숫자를 담고 있을 Stack 선언

2. while() + if()

    - reverseNumbers가 비어있지 않을 동안,

    - reverseNumbers의 마지막 수가 numbers의 배열값보다 크다면 answer에 뒤에서 큰 값으로 입력

    - 만일, 큰 값이 없을 경우에는 reverseNumbers에서 제거

3. if(reverseNumbers.isEmpty())

    - 만일 큰 값이 없어 reverseNumbers이 비게 될 경우, -1 반환

4. reverseNumbers.push(numbers[i])

    - ⭐ 위치 중요

    -  마지막에 값을 reverseNumbers에 입력하여 reverseNumbers와 numbers가 index를 달리하여 움직이게 할 수 있음

 

import java.util.Arrays;
import java.util.Stack;
 
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
 
        Stack<Integer> indexNumber = new Stack<>();
 
        Arrays.fill(answer, -1);
 
        for (int i=0; i < numbers.length; i++) {
            while (!indexNumber.isEmpty() && (numbers[indexNumber.peek()] < numbers[i])) {
                answer[indexNumber.pop()] = numbers[i];                    
            }
            indexNumber.push(i);
        }
        return answer;
    }
}
 

1. Stack<Integer> indexNumber

    - index를 담아줄 Stack 선언

2. Arrays.fill(answer, -1)

    - 기본값으로 -1 대입

3. while 반복문

    - ⭐ &&을 함께 주지 않을 경우, 무한 Loop에 빠질 수 있음에 유의

    - numbers[indexNumber.peek()] < numbers[i])

         - indexNumber에 위치한 numbers 값보다 다음 값(i번째 numbers 값)이 클 경우에만 answer의indexNumber 위치에 뒤에 있는 큰 수 대입

        - 만일 해당하는 값이 없을 경우, 기본값 -1로 출력 예정(indexNumber에는 해당 값이 남아 있게 됨)

4. indexNumber.push(i)

    - ⭐ 앞 뒤 값의 비교를 위해서 push를 가장 마지막에 위치

    - (push를 while 반복문보다 앞에 위치시킬 경우, numbers[indexNumber.peek()] < numbers[i])  이 부분에서 계속 동일한 값을 비교하면서 최종 결과가 -1이 반환됨)

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

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

 

[프로그래머스] - 뒤에 있는 큰 수 찾기(LV2) java