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

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

✍️ 첫번째 접근

2중 for문을 사용하고 싶은 마음이 근질근질하지만..4 ≤ numbers의 길이 ≤ 1,000,000라는 조건을 보면 싹 사라진다.
N이 최대 1,000,000이므로 최대 O(NlogN)으로 끊어야한다.
stack 개념을 사용함으로써 접근하였는데 예를 들어 stack 안에 2가 있으면 현재 2보다 뒤에 있는 큰 수를 찾지 못했서 stack에 있을 의미한다.
numbers에 있는 각 원소를 접근할 때마다 stack에 넣는다. 넣기 전에, stack에 무언가 있으면 제일 최근에 들어간 값과 현재 접근한 값과 비교를 하여 현재 접근한 값이 더 크다면 뒤에 있는 큰 수를 찾은 것이다. 찾았으므로 stack에 있는 제일 최근에 들어간 값을 remove해준다.
이러한 방식으로 푼다면 stack에는 값이 남아있을 수도 있는데 남아있는 값은 자신보다 뒤에 있는 큰 수가 없음을 의미한다. 맨처음에 result 배열을 -1로 초기화했기 때문에 따로 구현하지도 않아도 된다.

import Foundation

func solution(_ numbers:[Int]) -> [Int] {
    var result: [Int] = Array(repeating: -1, count: numbers.count)  // 큰 수가 될 수 없을 수도 있으므로 -1로 초기화
    var s: [(x:Int, idx: Int)] = []
    for i in 0..<numbers.count {
        while !s.isEmpty {
            let cur = s.last!
            if numbers[i] > cur.x { // 큰 수 찾음
                s.removeLast()
                result[cur.idx] = numbers[i]
            }
            else {
                break
            }
        }
        s.append((x:numbers[i],idx: i))
    }
    
    return result
}