[Swift/프로그래머스] 뒤에 있는 큰 수 찾기 ( 그리디 )

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

프로그래머스

 

이 문제의 특징은 바로 뒤의 숫자가 크면 해당 위치에 큰 숫자를 집어넣는것인데.

 

만약 뒤의 숫자가 같고 그 뒤의 숫자가 더 크다면 두 숫자의 위치에 큰 수를 할당해줘야한다는 것이 문제다.

 

첫번쨰 풀이

import Foundation

func solution(_ numbers:[Int]) -> [Int] {
    var dp = [Int](repeating: -1, count:numbers.count)
    for i in 0..<dp.count-1{
        if numbers[i] < numbers[i+1]{
            dp[i] = numbers[i+1]
        }
    }
    return dp
}

 

 

위의 경우를 고려하지 않고 해결한 방법이어서 오답이 나왔다.

 

하지만 이것도 잘못 이해한 문제였다

 

같은 수가 아니라 단순히 자기보다 큰 수를 입력해야하는 것이었다.

 

두번째 풀이

import Foundation

func solution(_ numbers:[Int]) -> [Int] {
    var dp = [Int](repeating: -1, count:numbers.count)
    for i in 0..<dp.count-1{
        if numbers[i] < numbers[i+1]{
            dp[i] = numbers[i+1]
        }
    }
    
    for i in stride(from:numbers.count-1, through:1, by:-1){
        if numbers[i] == numbers[i-1]{
            dp[i-1] = dp[i]
        }
    }
    
    return dp
}

 

세번째 풀이

import Foundation

func solution(_ numbers:[Int]) -> [Int] {
    var dp = [Int](repeating: -1, count:numbers.count)
    for i in 0..<dp.count{
        for j in i..<dp.count{
            if numbers[i] < numbers[j]{
                dp[i] = numbers[j]
                break
            }
        }
    }
    return dp
}

 

이것도 시간초과가 난다.

 

정답

import Foundation

func solution(_ numbers:[Int]) -> [Int] {
    var result = [Int](repeating: -1, count: numbers.count)
    var stack: [(index: Int, value: Int)] = []
    
    // 배열을 왼쪽부터 순회하면서 처리
    for i in 0..<numbers.count {
        // 현재 숫자가 스택의 top에 있는 숫자보다 크다면,
        // 현재 숫자가 스택에 있는 숫자의 뒷 큰수가 됨
        while !stack.isEmpty && stack.last!.value < numbers[i] {
            let last = stack.removeLast()
            result[last.index] = numbers[i]
        }
        // 현재 인덱스와 값을 스택에 추가
        stack.append((i, numbers[i]))
    }
    
    return result
}

 

쉽지않다.