[프로그래머스] 큰 수 만들기

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

✍️ 첫번째 접근

input으로 들어온 number가 문자열이므로 각 인덱스에 쉽게 접근하기 위해서 Int 배열에 하나씩 담는다.
k개의 수를 제거했을 때 제일 큰 수를 만들어야하므로, number를 처음부터 끝까지 돌면서 i번째 값이 i+1번째 값보다 작다면 i번째 값을 삭제하고 k개를 삭제할 때까지 다시 number를 처음부터 끝까지 돈다.
하지만, 이렇게 할 경우 remove 메서드의 시간 복잡도는 O(n)이므로 시간 초과가 발생하였다. 혹여나 고차함수로 인한 시간 초과인가 싶어서 고차함수를 대체하는 등을 하였지만 여전하였다.

import Foundation

extension String {
    subscript(_ index: Int) -> Character {
        return self[self.index(self.startIndex, offsetBy: index)]
    }
}

func solution(_ number:String, _ k:Int) -> String {
    var arr: [Int] = []
    for i in number {
        arr.append(Int(String(i))!)
    }
    var cnt = k
    while cnt > 0 {
        for i in 0..<arr.count-1 {
            if arr[i] == 9 {
                continue
            }
            if arr[i] < arr[i+1] {
                arr.remove(at: i)
                break
            }
        }
        cnt -= 1
    }
    if arr.count == number.count {
        return String(number.prefix(number.count-k))
    }
    var answer: String = ""
    for i in arr {
        answer += String(i)
    }
    return answer
}

✍️ 두번째 접근

remove 메서드의 시간 복잡도로 인해 시간 초과가 발생하였으니 시간 복잡도가 O(1)인 removeLast 메서드를 사용하고자 stack 형태의 배열을 사용하였다.
그리고 number의 모든 인덱스를 계속해서 접근했던 첫번째 접근과 달리 각 인덱스를 한번씩만 접근하게 하여 문제를 해결하였다.

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    var stack: [Int] = []
    var arr = number.map{ Int(String($0))! }
    var cnt: Int = 0
    for i in 0..<arr.count {
        while !stack.isEmpty && stack.last! < arr[i] && cnt < k {
            stack.removeLast()
            cnt += 1
            if cnt == k {
                break
            }
        }
        stack.append(arr[i])
    }
    if stack.count == number.count {
        return String(number.prefix(number.count-k))
    }
    return stack.reduce("") { $0 + "\($1)" }
}