42883. 큰 수 만들기

[lenaios]

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

[eeeesong]

10번 시간초과 해결 못했는데 시간복잡도 고쳐봐도 안돼서 모르겠습니다..🥲

https://github.com/eeeesong/algorithm/blob/master/프로그래머스/level2_1.md

-> 둠바 블로그 팁 보고 해결!! 감사합니당

[ghis22130]

https://ghis22130.github.io/2021-07-08-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4_%ED%83%90%EC%9A%95%EB%B2%95_-%ED%81%B0%EC%88%98%EB%A7%8C%EB%93%A4%EA%B8%B0/

[zekexros]

시간초과 해결 못했는데 스터디하는 날 해결하신분의 설명을 직접 듣고 싶어 보류하겠습니다. 🙂

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    var answer = [Int]()
    var n = k
    var index = 0
    let intNumber = number.map{Int(String($0))!}
    while answer.count != number.count - k {
        if let indexWithNine =  intNumber[index...n].firstIndex(of: 9) {
            index = indexWithNine + 1
            n += 1
            answer.append(9)
            continue
        }

        let maxNumber = intNumber[index...n].enumerated().max { left, right in
            return left.element < right.element
        }
        index += maxNumber!.offset + 1
        n += 1
        answer.append(Int(exactly: maxNumber!.element)!)
    }
    return answer.map{String($0)}.joined()
}

[ghis22130]

@zeke-iOS
짐작되는 거는

number.map{Int(String($0))!}

이거는 while 밖으로 빼줘서 한번만 처리해주게끔 하는게 좋을 것 같아요! 만약 number = 99999999999999999...9999999 이렇게 되면 이만큼 계속 Int 배열로 바꿔주는게 반복문 실행될때마다 생기니까요!

그리고 결정적인건 max때문일거에요 ㅜ 저도 max썻을때 테케 하나 시간 초과 계속 낫는데

max는 배열을 다 순회하면서 max 값을 찾는데 (91111111111111)의 경우 9를 찾으면 바로 순회를 멈추면 되니 max 값 처리하는 로직을 따로 처리해줘야할것 같아요! (한자릿수의 최대 값은 9라고 한정되있으니) (81111111111119)같은 경우는 전체를 순회해야겠지만 🥲

[lenaios]

테스트 케이스 10번 시간 초과합니다.😥

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    var deleted = 0
    var stack = [String]()
    var numbers = number.map(String.init)

    while deleted < k && numbers.count > 0 {
        guard let last = stack.last else {
            stack.append(numbers.removeFirst())
            continue
        }
        if last < numbers.first! {
            stack.removeLast()
            deleted += 1
            continue // tip!
        }
        stack.append(numbers.removeFirst())
    }
    // 다 지웠는데 numbers가 남아있다면 뒤에 붙이기
    if deleted == k && numbers.count > 0 {
        stack.append(contentsOf: numbers)
    }

    // k가 남았는데 numbers가 빈 경우, k만큼 뒤에서부터 삭제
    if deleted < k && numbers.count == 0 {
        stack.removeLast(k - deleted)
    }
    return stack.joined()
}