프로그래머스 뒷 큰수 스택 풀이 - 자바스크립트 풀이

프로그래머스

레벨2 도장깨기 중에 만난 문제인데 여태 풀었던 레벨2 중에 제일 풀기 힘들었던 문제였다. 이게 레벨2 맞나...?

안 어렵다고? ㅇㅇ 축하한다.

사실 이번 문제는 내 힘으로 못 풀었다. 질문하기 힌트보고 겨우 풀었다. 자수한다. 이제 풀이 들어간다.

stack을 사용하여 문제를 풀라는 힌트에 한 10분 동안 뇌가 정지되었다. 스택을 어디에 어떻게 사용하란건지

처음에 for문과 while문으로 막힘없이 슉슉 작성하고 O(n*n)의 시간복잡도와 함께 시간 초과를 맛보고 온 후 머리가 더 굴러가지 않았다. 

머리가 지끈지끈

휴 😮‍💨 stack을 이용하여 문제를 풀어보자.

let stack = [];

변수 stack에는 뒷 큰수 값을 구하지 못한 숫자의 인덱스를 차곡차곡 담아둘 것이다.

let answer = new Array(numbers.length).fill(-1);

answer는 최종 반환값을 위한 변수이다. 문제에서 뒷 큰수가 없는 값들에 대해서는 -1로 표시하도록 명시했으므로 우선 모든 요소들의 값을 -1로 설정한다. 

numbers 요소를 하나씩 돌면서 뒷 큰수를 구하지 못한 값보다 큰 값을 발견하면 뒷 큰수를 발견한 것이므로 stack에서 즉시 해당 값에 대한 인덱스는 제거해주고 뒷 큰수를 할당해줄 것이다.

예제와 함께 살펴보자.

예제: numbers가 [2, 3, 3, 5]인 경우

i = 0, numbers[i] = 2
→ stack = [0] (2의 인덱스 저장) // 뒷 큰수 발견하지 못했으므로 stack에 인덱스 저장

i = 1, numbers[i] = 3
→ 3 > 2 (stack에서 pop, answer[0] = 3) // 뒷 큰수 발견! stack에서 인덱스 삭제
→ stack = [1] (3의 인덱스 저장)

i = 2, numbers[i] = 3
→ stack = [1, 2] (동일한 값이므로 그냥 저장) // 뒷 큰수 발견하지 못했으므로 stack에 인덱스 저장

i = 3, numbers[i] = 5
→ 5 > 3 (stack에서 pop, answer[2] = 5) // 뒷 큰수 발견! stack에서 인덱스 삭제
→ 5 > 3 (stack에서 pop, answer[1] = 5) // 뒷 큰수 발견! stack에서 인덱스 삭제
→ stack = [3] (5의 인덱스 저장)

이 예제를 토대로 코드를 작성해보자.

최종 코드 

시간복잡도는 O(n)이다.

function solution(numbers) {
    let answer = new Array(numbers.length).fill(-1);
    let stack = [];
    for(let i = 0; i < numbers.length; i++){
        while(stack.length > 0 && numbers[i] > numbers[stack.at(-1)]){
            answer[stack.at(-1)] = numbers[i];
            stack.pop();
        }
        stack.push(i);
    }
    return answer;
}

해당 코드는 numbers 배열의 앞에서 뒤로 가는 방향으로 탐색을 하는 방식이었다.

하단의 코드는 뒤에서 앞으로 탐색하는 방법을 채택한 코드이다. 이 코드도 같이 봐두자.

function solution(numbers) {
    let n = numbers.length;
    let answer = new Array(n).fill(-1);
    let stack = [];

    for (let i = n - 1; i >= 0; i--) { // 뒤에서 앞으로 탐색
        while (stack.length > 0 && stack[stack.length - 1] <= numbers[i]) {
            stack.pop(); // 현재 값보다 작은 값은 필요 없으므로 제거
        }
        if (stack.length > 0) {
            answer[i] = stack[stack.length - 1]; // 뒷 큰수 설정
        }
        stack.push(numbers[i]); // 현재 값을 스택에 추가
    }

    return answer;
}