[스택] 뒤에 있는 큰 수 찾기

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

가장 가까이 있는 => 스택

첫풀이 (시간초과)

1. 배열 모든 원소를 -1로 초기화 
2. 뒤에서부터 numbers 순회
3. stack에 numbers의 뒷 부분부터 넣고 뒤에서부터 순회하면 가장가깝고 큰수를 찾는다

// 뒤에서부터
// curr < prev가 있으면 prev로
function solution(numbers) {
    var answer = Array.from({length: numbers.length}, () => -1);
    const stack = [numbers[numbers.length-1]];
    
    for (let i = numbers.length-1; i >= 0 ; i--) {
        const curr = numbers[i];
        
        // stack안에서 가까운 큰수 찾기
        for (let j = stack.length-1; j >= 0; j--) {
            const previous = stack[j];
            // 전 > 현재
            if (previous > curr) {
                answer[i] = previous;
                break;
            }
        }
        stack.push(curr);
    }
    
    return answer;
}

 

최종풀이

O(N^2) 보다 O(N)이나, O(NlogN)방법을 생각해봤다

현재보다 작거나 같은 전의 값은 제거해서 내부순회의 시간복잡도를 줄였다. 

// 뒤에서부터 순회하여 자기보다 큰값을 찾을때까지 
function solution(numbers) {
    const answer = Array.from({length: numbers.length}, () => -1);
    const stack = [];
    
    for (let i = numbers.length-1; i >= 0; i--) {
        const curr = numbers[i];
        // 현재보다 작거나 같은 수는 제거한다
        while (stack.length && stack[stack.length-1] <= curr) {
            stack.pop();
        }
        // 작은수를 모두 제거한 뒤 남은 큰 수가 있으면 answer에 부여해준다
        if (stack.length) {
            answer[i] = stack[stack.length-1];
        }
        stack.push(curr);
    }
    return answer;
}