뒤에 있는 큰 수 찾기

링크

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

문제

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

문제풀이

문제 자체는 간단하게 나와있는 그대로 해석해서 풀면되는데 있는 그대로 풀게되면 시간초과 때문에 문제가 해결되지 않는다. 따라서 시간 복잡도를 줄이는 코드로 작성되야 한다.

시간복잡도를 고려하지 않는다면 단순하게 numbers 배열에서 맨 앞의 요소를 가져와서 다시 numbers의 요소들중 뽑아온 정수보다 큰 수를 찾아내면된다.

문제 해결 시간을 고려하면 위와 같은 경우에는 극단적으로 좋지못한 케이스의 경우에 시간 내에 해결이 불가능할 수 있다.

따라서 시간을 줄이기 위해서 스택의 개념을 도입하여 문제를 해결한다.

가장 먼저 문제 해결에 있어서 중요한 점은 numbers 배열의 뒤에서부터 문제를 해결해 나가는 것이다. 앞에서부터 순서대로 문제를 해결하게되면 현재 비교하려는 숫자의 뒤에 어떤 숫자들이 나올지 알 수 없기 때문에 뒤에서부터 해결하도록 코드를 작성한다.

뒤에서부터 반복문을 진행해서 현재 요소보다 큰 값이 스택 안에 존재하는지 확인한다. 해당 과정은 이중 반복으로 구성되도록 코드를 작성한다. 이중 반복으로 인해서 시간초과의 위험이 있지만 스택의 내용 중에 매 반복마다 사용되지 않을 값을 삭제하여 반복을 최소화한다.

스택과의 비교로 큰 값을 찾으면 스택의 해당 값을 반환해줄 배열에 추가하고 스택 내에서 현재 비교중인 값보다 작은 값을 현재 비교중인 값보다 큰 값이 나올 때까지 삭제한다. 그리고 현재 비교값을 스택에 넣어준다.

해당 과정을 반복하면 원하는 값을 얻을 수 있다.

주의할 점으로 배열의 조작은 push와 pop으로만 진행한다. shift, unshift의 경우에 가장 앞의 값을 조작할 경우에 그 뒤의 내용들을 모두 한번씩 참조하여 앞으로 이동, 뒤로 이동하는 작업이 추가되기 때문에 시간적인면에서 push, pop은 1, shift, unshift는 n 만큼의 시간을 잡아먹는다.

따라서 스택, 반환할 배열 등 모두 push, pop으로 조작하고 마지막에 reverse 함수를 사용해 배열을 뒤집어 반환하는 것으로 코드를 마무리한다.

코드

// stack을 활용
// 문제 해결을 위해서 뒤에서부터 정수 배열을 스택에 넣어가며 스택 안에 현재 수보다 큰 수가 있는지 확인한다.

// [2, 3, 3, 5] => [5, 3, 2]

// shift, unshift가 속도면에서 push, pop에 비해서 엄청 오래걸리므로 해당 내용 변경
//   => 배열에서 하나를 삭제, 넣고 나머지를 뒤로 미루거나 앞으로 당겨오는 작업때문에 배열 전체를 다시 돌아야해서 시간이 오래걸림

// result도 똑같이 생성해서 마지막에 reverse 시키는 방식으로 코드 변경

function solution(numbers) {
    let result = []
    let stack = []
    
    for(let i = numbers.length - 1; i >= 0; i--) {
        let now = numbers[i]
        let check = true
        
        // 스택 안의 요소를 가지고 자신보다 큰 가까운 요소 찾기
        for(let i = stack.length - 1; i >= 0; i--) {
            if(now < stack[i]) {
                result.push(stack[i])
                check = false
                break
            }
        }
        // 없으면 -1 넣기
        if(check) result.push(-1)
        
        // 스택에서 현재요소보다 작은 숫자는 날리기
        while(true) {
            
            if(now >= stack[stack.length - 1]) {
                stack.pop()
            } else {
                break
            }
        }
        // console.log(now, stack, result)
        
        // 스택에 현재 요소 저장
        stack.push(now)
    }
    
    return result.reverse()
}