[JS] 뒤에 있는 큰 수 찾기

처음에는 무식하게 반복문을 두번 사용해서 찾는 방식으로 구현했었는데, 배열의 크기가 100만개이다보니 예상대로 시간초과가 발생하였다.

 

메모제이션이나 스택을 활용하면 좋을 것 같아서 생각을 하다가 스택을 활용해서 구현하였다.

 

1. 스택에 맨 끝값을 집어넣고 해당 값을 -1로 만들어 준다.

2. 배열을 뒤에서부터 구해준다. 스택에서 비교할 값을 pop으로 빼주고, 만약 스택에서 뺀 값이 비교할 값보다 작으면 큰 수가 나오거나 스택이 비어질때까지 계속 값을 빼준다.

3.  n-1 번째와 n번째를 비교할때, n이 n-1번째보다 크다면 무조건 뒷 큰수는 n이된다. 따라서 해당 경우 n을 n-1의 뒷 큰수로 만들어주고, 스택에 다시 두개의 값을 집어 넣는다.

4. 스택이 비어있는경우 -1으로 생각하고 원래 있던 값을 스택에 넣어준다.

 

 

 

function solution(numbers) {
    const stk = [numbers[numbers.length-1]]
    numbers[numbers.length-1] = -1
    for (let i = numbers.length-1 ; i>0 ; i--){
        
        let num = stk.pop()
        
        while (stk.length && num <= numbers[i-1]) num = stk.pop()
    
        if ( num > numbers[i-1]) {
            stk.push(num)
            stk.push(numbers[i-1])
            numbers[i-1] = num
        } else if (!stk.length){
            stk.push(numbers[i-1])
            numbers[i-1]  =  -1
        }
    }
    return numbers
}