Swift) 프로그래머스(Lv2) - 큰 수 만들기 (Stack)

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

코딩테스트 연습 - 큰 수 만들기

안녕하세요! 후르륵짭짭 입니다.

어,,,, 이 문제는 제 기준에서 많이 어려웠습니다....

어떻게,,, 해야할지 고민이 많았고,,,,,

결국 도움을 받아서 풀었지만,,,, Swift에서는 ㅎㅎㅎ 시간초과,,, 쩝,,,

일단 어떻게 해결한 방법을 올려 보도록 하겠습니다.

 

** 저의 방법 **

func solution(_ number:String, _ k:Int) -> String {
    
    let maxCnt = number.count - k
    let arrayNum = Array(number).map { (char) -> Int in
        return Int(String(char))!
    }
    
    var answerList : [Int] = []
    var k = k
    for (index , element) in arrayNum.enumerated() {
        
        if k != 0 {
        
        //최대로 넣을 수 있는 수 : 234 에 9 가 들어오면 234가 살아져 버리니 방지용이다.
            var maxRemove = arrayNum.count - index >= maxCnt ? maxCnt : arrayNum.count - index
           
            while maxRemove > 0 && !answerList.isEmpty && answerList.last! < element && k > 0{
                answerList.removeLast()
                k -= 1
                maxRemove -= 1
            }
            
        }
        
        if answerList.count < maxCnt {
                
            answerList.append(element)
            
        }
        
//        print(index , k , answerList)
        
    }
    
    return answerList.map { (element) -> String in
        return String(element)
    }.reduce("", +)
}

처음에,, 일단 Int 형으로 바꿔 줍니다 (그래야 접근 속도가 빨라집니다. - 시간 초과 방지를 위해서 )

그리고 모든 요소를 하나씩 탐색 할 겁니다. 이제 규칙이 생깁니다.

예를 들어, 29482 라 하고 지울 수가 K = 2 라고 한다면 우리는 총 4자리를 반환해야합니다.

그래서 다음과 같은 규칙으로 넣어 집니다.

2  | (2 - 삭제) 9 | 94 | 9(4 - 삭제)8 | 9482

이 문제의 규칙은 일단 숫자를 넣는데, 다음 숫자가 더 크다면 앞에 숫자를 제거 해주는 겁니다.

제거해주는 동시에 K의 숫자도 줄여 줍니다.

그런데, 최대 삭제 숫자를 넘기면 안되니깐, K가 0일 때면 그 뒤에 숫자를 넣어줍니다.

(삭제 하게 된다면 stack의 길이는 maxCnt 보다 작아지게 될 겁니다.)

 

** 시간초과 방법 **

func solution2(_ number:String, _ k:Int) -> String {
    
    var returnSize = number.count - k
    let arrayNum = Array(number).map { (char) -> Int in
        return Int(String(char))!
    }
    
    var index = -1
    var numList : [Int] = []
    
    while returnSize > 0 {
        
        var tempIndex = 0
        var maxElement = -1
        
        for search in (index + 1)...(number.count - returnSize){
            
            let searchNum = arrayNum[search]
            
            if maxElement < searchNum {
                maxElement = searchNum
                tempIndex = search
                
                if maxElement == 9 {
                    break
                }
            }
            
        }
        
        index = tempIndex
        numList.append( arrayNum[index] )
        returnSize -= 1
        
    }
    
    let answer : [String] = numList.map { (element) -> String in
        return String(element)
    }
    
    
    return answer.joined()
}

처음에 이 문제를 어떻게 해결 해야할지 몰라서,,, 인터넷에 뒤졌다가  발견한 방법인데,,,

이 방법으로 하면 시간 초과가 발생합니다...

제가 코드를 잘 못 한 걸 수도 있는데,,,