문제 풀이 아이디어

numbers의 길이가 최대 1,000,000이기 때문에 일일히 완전탐색을 통해서 뒷큰수를 구할 수는 없습니다. stack을 사용해서 stack.last보다 크면 pop, 작으면 push를 하면 stack 내부가 오름차순으로 정렬되는 원리를 사용하는 문제입니다.

예전에 백준에서 풀었던 오큰수라는 문제와 완전히 동일한 문제입니다. 자세한 설명은 이 포스팅을 참고해주세요.

코드

func solution(_ numbers:[Int]) -> [Int] {
    
    // 아직 뒷큰수를 구하지 못한 index를 넣어두는 스택
    var stack = [0]
    
    // 현재 뒷큰수가 될 수 있는 인덱스
    var index = 1
    
    // ans[index] = numbers[index]의 뒷큰수
    var ans = Array(repeating: -1, count: numbers.count)
    
    // numbers의 모든 index를 순회
    while index < numbers.count {
        // 현재 index가 stack.last에 있는 index이 뒷큰수가 될 수 있는 경우
        while !stack.isEmpty && numbers[stack.last!] < numbers[index] {
            // stack.last를 pop하고 뒷큰수를 기록함
            ans[stack.popLast()!] = numbers[index]
        }
        
        // 현재 index가 더 이상 stack.last의 뒷큰수가 될 수 없는 경우
        stack.append(index) // 현재 index의 뒷큰수를 구하기 위해서 stack에 넣고
        index += 1 // index를 1 늘린다
    }
    
    return ans
}