[프로그래머스] 뒤에 있는 큰 수 찾기(Level 2) 스택 Stack

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/154539

1. 문제 요약

• 주어진 배열 numbers에서 각 값의 뒷쪽 값 중 큰 값을 찾아 새로운 배열에 담아서 반환한다.
• 해당 값보다 큰 값이 없을 경우 -1을 넣는다.

2. 핵심 아이디어

• greedy 방식으로 탐색하게 되면 시간복잡도 이슈로 오답.
• Stack에 찾아야 할 index를 담아두고 numbers의 값과 비교하여 반복작업 규모를 줄인다.

3. 풀이 코드

public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];

        Stack<Integer> stack  = new Stack<>();
        Arrays.fill(answer, -1);

        for(int i = 0; i < numbers.length; i ++){
            while(!stack.isEmpty() && numbers[stack.peek()] < numbers[i]){
                int idx = stack.pop();
                answer[idx] = numbers[i];
            }

            stack.push(i);
        }

        return answer;
    }

4. 회고 및 느낀점

• Stack 혹은 Queue 등 자료구조를 적절히 활용하면 시간복잡도를 크게 낮출 수 있다는 것을 느꼈다.

내 오답 : 처리는 가능하나 시간이 너무 오래걸림

public int[] solutionOld(int[] numbers) {
        int[] answer = new int[numbers.length];

        //시간복잡도  O(N^2)
        for(int i = 0; i < numbers.length -1; i ++){
            for(int j = i + 1; j < numbers.length; j ++ ){
                if(numbers[i] < numbers[j]){
                    answer[i] = numbers[j];
                    break;
                }
            }
        }

        for(int i = 0; i < answer.length; i ++){
            if(answer[i] == 0) answer[i] = -1;
        }

        return answer;
    }