프로그래머스 - 뒤에 있는 큰 수 찾기

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

2. 접근 방식

단순히 이중 for문으로 접근하면 시간 초과가 발생하는 케이스가 있다. 당연하겠지만.. 이 문제의 해결법은 2중 for문의 시간을 단축시키는데 있다. 

 

핵심은 다음과 같다.

테케를 예로 들면 아래와 같은 배열에서

9

1

5

3

6

2

answer의 2,3번째 인덱스의 값이 6임을 알 수 있다.

즉, 큰 수가 나올 때까지 탐색을 하고, 그 사이의 모든 수들의 뒷 큰수 값은 같다는 뜻이다.

 

또 다른 예로 아래와 같은 배열에선

6

5

4

3

2

1

7

9

8

10

answer의 1~5번째 까지의 값이 7이라는 것을 알 수 있다. 

대표적으로Stack을 이용해 구현할 수 있다.

단, 해당 인덱스의 값을 넣는게 아닌 인덱스 자체를 넣어서 비교해주는 것이 중요하다.

 

처음 Stack이 비어있기 때문에 Stack에 배열의 첫번째 값을 넣어준다.

1번째 인덱스부터 값을 비교하며 작은 수일 때는 Stack에 인덱스를 넣어주고

큰 수일 경우엔 pop을 해주면 해당 인덱스에 값을 넣어준다.

 

3. 구현

import java.util.*;

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

4. 정리

이전에 백준에서 비슷한 문제(사실 똑같은 문제 => 백준 17298번)를 풀어 맞출 수 있으리라 기대했지만 결국 예전에 풀었던 방식을 참고했다. 다만 문제 접근 방법 자체는 맞았지만 구현에서 시간이 부족해 틀린게 좀 아쉽다. Stack은 전혀 생각을 못했고 다른 방법으로 충분히 구현 할 수 있었을 거란 아쉬움이 남는다.