프로그래머스 뒤에 있는 큰 수 찾기 ( LV 2 )

https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=java

프로그래머스

 

* 문제 제목 그대로 뒤에 있는 숫자중 가장 큰 숫자를 고르는 것이다. + 제일 가까이 있는 숫자중에서.

* 처음에는 BruteFroce를 돌려서 현재 숫자보다 큰 숫자가 등장하면 break를 걸고 결과를 갱신하는 코드를 작성했는데 시초가 났다.

* 아무리 짱구를 굴려봐도 답이 안나와서 GPT한테 물어봤다.

 

* Stack을 활용하면 O(N) 시간 복잡도로 끝낼수 있다.

* 알고리즘 흐름을 설명하면.

 1) numbers 길이만큼 반복문을 돌리는데 뒤에서 부터 순차적으로 탐색한다.

 2) Stack.peek()의 값과 비교하여 numbers의 제일 뒤에 값과 비교하여 numbers 값이 더 크면 pop() 한다.

 3) 즉 Stack에는 현재 for 루프의 index 와 비교했을때 뒤에 있는 숫자중 가장 가깝고 큰 수를 제일 위에 할당하는 것이다.

 4) 스택이 비었으면 뒤에 큰 값이 없으니 -1 스택에 값이 있으면 그 값을 할당하면된다.

 5) 마지막으로 numbers[i] 값을 push 하며 1번부터 반복한다.

 

import java.io.*;
import java.util.*;

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

 

- 구현된 코드이고,, Stack의 개념을 아는것과 활용하는 것은 차이점이 있다는 것을 알았다.. 잘 숙지하자.