[Algorithm] 프로그래머스 - 뒤에 있는 큰 수

🧐 문제

프로그래머스: 뒤에 있는 큰 수 찾기

🧙 문제풀이

만만하게 봤지만(?) 생각할 거리가 꽤 있는 문제였다. 첫번째는 일단 무식하게 풀어보자였다. Array를 내 위치부터 잘라서 그 뒤로 해당 숫자보다 큰 숫자를 찾아서 반환해줬다. 하지만 당연하게도 시간초과가 났다. numbers의 길이가 최대 1,000,000이기 때문에 아래와 같은 풀이 방법은 결국 O(n^2)으로 시간초과가 나게 된다.

func solution(_ numbers: [Int]) -> [Int] {
    var answer: [Int] = []
    
    for i in numbers.indices {
        let first = numbers[i...].first { $0 > numbers[i] } ?? -1
        answer.append(first)
    }
    
    return answer
}

시간복잡도를 줄일 수 있는 방법이 없을까? 자신보다 뒤에서 가장 가까이 있는 큰수이기 때문에 현재 숫자가 stack에 쌓인 수보다 클 경우 stack에서 pop해주고, 더이상 큰수가 아닐때 append를 시켜주면 된다고 생각했다. 이렇게 된다면 결국 반복문 1회 + while에서 배열은 무조건 한번씩 빠지는 것이기 때문에 O(n)의 시간복잡도로 해결이 된다.

func solution(_ numbers: [Int]) -> [Int] {
    let n = numbers.count
    var stack: [Int] = []
    var answers: [Int] = Array(repeating: -1, count: n)
    
    for i in 0..<n {
        while let last = stack.last, numbers[last] < numbers[i] {
            answers[last] = numbers[i]
            stack.removeLast()
        }
            
        stack.append(i)
    }
    
    return answers
}