[프로그래머스/Swift] 154539번 - 뒤에 있는 큰 수 찾기

풀이

1. 스택이 비어있다면 삽입
2. if 현재의 값 < 스택의 last 값 { 스택에 push }
3. if 현재의 값 ≥ 스택의 last 값 { 스택의 last 값이 현재의 값보다 작을때 까지 pop }
4. pop한 값은 결과에 저장 ( 저장할 때 해당 값 보다 큰 첫수는 스택의 last )
5. if pop 하는데 스택이 비어 있으면 큰 첫수가 없기에 -1 저장
6. 3번 이후 스택에 push
7. 전체 numbers를 완료 후, 스택이 비어있지 않으면 스택이 빌때까지 pop(4,5) 실행

func solution(_ numbers:[Int]) -> [Int] {
    var result: [Int] = [Int](repeating: -1, count: numbers.count)
    var stack: [(Int, Int)] = [] // $0: arrs의 Index, $1: arrs의 number
    var idx = numbers.count - 1 // 뒷쪽부터 접근
    while idx >= 0 {
        let num = numbers[idx] // 현재 값
        while !stack.isEmpty && num >= stack.last!.1 { // 현재 값보다 작은 것은 전부 삭제
            let last = stack.removeLast()
            result[last.0] = (stack.last ?? (-1, -1)).1
        }
        stack.append((idx, num))
        idx -= 1
    }
    while !stack.isEmpty { // stack에 남은 것들 정리
        let last = stack.removeLast()
        result[last.0] = (stack.last ?? (-1, -1)).1
    }
    return result
}

틀린 소스 - 시간초과

• 반복문을 이용한 단순 비교

func solution(_ numbers:[Int]) -> [Int] {
     // 필수한 프로퍼티 선언
     let maxIdx: Int = numbers.count - 1 // 접근용 인덱스 - 최대 인덱스
     var resultArr: [[Int]] = [[Int]](repeating: [Int](repeating: 0, count: 3), count: maxIdx + 1) // [0]: 가장큰수, [1]: 큰수의인덱스, [2]: 결과
     
     // 초기값 등록
     resultArr[maxIdx][0] = numbers[maxIdx]
     resultArr[maxIdx][1] = maxIdx
     resultArr[maxIdx][2] = -1
     
     var idx = maxIdx - 1
     while idx >= 0 {
         let number = numbers[idx]
         if number >= resultArr[idx+1][0] {
             resultArr[idx][0] = number // 가장 큰수 등록
             resultArr[idx][1] = idx // 큰수의 인덱스 등록
             resultArr[idx][2] = -1 // number보다 큰 수가 없었으니 -1
         }else { // 현재까지 가장 큰 수 보다 number가 작음 - 결과값을 찾아야함
             resultArr[idx][0] = resultArr[idx+1][0] // 가장 큰수 등록
             resultArr[idx][1] = resultArr[idx+1][1] // 큰수의 인덱스 등록
             resultArr[idx][2] = -1 // 우선 -1 넣고 변경
             //자기보다 처음 큰 수를 찾아야함 ( 가장 큰수의 인덱스 뒤로는 확인할 필요없음 )
             for i in idx...resultArr[idx][1] {
                 if number < numbers[i] { // number보다 큰 수를 찾음
                     resultArr[idx][2] = numbers[i]
                     break
                 }
             }
         }
         idx -= 1
     }
     return resultArr.map{ $0[2] }
 }