[Java] 프로그래머스(level-2) - 뒤에 있는 큰 수 찾기

문제 풀이

---

이번 문제는 Stack(스택)을 활용해 시간복잡도를 줄여 풀 수 있는 문제이다.

아이디어 도출

스택을 사용하지 않고 이중 for문으로 뒷 큰수를 찾을 경우 numbers의 범위가 1,000,000이기에 시간초과가 발생한다. 시간복잡도를 O(n)으로 줄이기 위해 스택을 활용해야 한다.

필자의 경우 스택에 [인덱스, 값] 형태를 삽입하여 현재 값과 스택의 정상값을 비교하며 뒷 큰수를 찾도록 구현하였다. 이를 위한 아이디어는 다음과 같다.

1. numbers 길이를 가지는 answer 배열을 선언한다.
2. 스택에 [인덱스, 값] 형태로 삽입한 후, numbers를 순회하며 현재 값이 이전 원소인 스택의 정상값보다 큰지 확인한다.
3. 현재 값이 스택의 정상값보다 큰지 확인하기 위해 스택이 빌 때까지 반복한다.
4. 이때, 뒷 큰수가 된다면 해당 값을 answer 배열에 이전 원소(스택 정상값)의 인덱스 위치에 갱신한다.
5. 현재 인덱스와 값으 스택에 삽입한다.
6. 2-5번 과정을 반복하며 numbers 순회가 끝나고 스택에 값이 남아있다면 뒷 큰수가 되지 못하는 수가 있는 것이기 때문에, 스택이 빌때까지 값을 추출하며 answer 배열에 -1로 갱신한다.

다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.

작성 코드

---

import java.util.*;

class Solution {

    public int[] solution(int[] numbers) {

        // 1. numbers를 순회하면서 현재 원소와 뒤의 원소들과 비교하며 더 큰수가 있는지 확인한다.
        // 2. 현재 원소보다 뒤에 큰 수가 있다면, 해당 수를 결과 배열의 같은 위치에 담는다.
        // 3. numbers의 범위가 최대 1.000.000이기에 시간초과를 고려해야 한다. -> O(n) 수준
        // 4. 이때, Stack을 활용해 현재 원소와 스택의 정상값을 비교해가며 뒷 큰수를 확인한다.

        int[] answer = new int[numbers.length];

        // 스택은 [인덱스: numbers값] 형식으로 담는다.
        Stack<int[]> st = new Stack<>();

        // 먼저 numbers의 첫번째 값을 담는다.
        st.push(new int[]{0, numbers[0]});
        
        for(int i=1; i<numbers.length; i++) {
            
            // 현재 인덱스의 값
            int num = numbers[i];
            
            // 현재 값(num)이 이전 원소(스택의 정상값=st.peek()[1])보다 클 경우 뒷 큰수를 충족한다.
            while(!st.isEmpty() && num > st.peek()[1]) {
                int[] toBig = st.pop();
                answer[toBig[0]] = num;
            }

            // 현재 인덱스와 값을 스택에 담는다.
            st.push(new int[]{i, numbers[i]});

        }

        // 뒷 큰수가 존재하지 않는 값들의 위치를 -1로 갱신한다.
        while(!st.isEmpty()) {
            answer[st.pop()[0]] = -1;
        }

        return answer;
    }

    public static void main(String[] args) {
        
        Solution sol = new Solution();
        
        // int[] numbers = new int[]{2, 3, 3, 5};
        int[] numbers = new int[]{9, 1, 5, 3, 6, 2};

        sol.solution(numbers);

    }

}

회고

- —

출처

- —

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.