[Swift] 프로그래머스 - 큰 수 만들기 (Level. 2)

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

시간초과 풀이 (백트래킹)

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    var answer = 0
    var visited = Array(repeating: false, count: number.count)
    var number = number.map { String($0) }
    
    func dfs(_ target: Int) {
        if target == k {
            var temp = ""
            
            number.enumerated().forEach {
                if !visited[$0.0] {
                    temp += number[$0.0]
                }
            }
            
            answer = max(answer, Int(temp)!)
            return
        }
        
        for i in 0..<number.count {
            if !visited[i] {
                visited[i] = true
                dfs(target+1)
                visited[i] = false
            }
        }
    }
    
    dfs(0)
    
    return String(answer)
}

- 테스트케이스 1번, 12번 제외하고 다 "core dumped", 시간 초과 에러가 떴던 코드이다.

- 백트래킹의 시간복잡도가 O(2^n) 임을 감안하면 number의 길이가 1,000,000만이니 매우 큰 수 이다.

 

그래서 문제 분류가 그리디로 되어있는 만큼 큰 수 만 골라서 조합을 하는 방법을 생각해봤는데,

입출력 예시 3번째에 1이 포함되어있는 것을 보니 작은 수만 k개만큼 제거해서 풀어내는 게 맞는 방법은 아니라는 생각이 들었다.

결국 풀이를 찾아보니 Stack 자료구조를 이용하는 풀이가 대다수여서, 해당 풀이를 이해해보고 다시 풀어보았다.

 

Stack 활용 풀이

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    var stack:[Int] = []
    let number = number.map { Int(String($0))! }
    
    var cnt = 0

    for i in 0..<number.count{
		// 새로들어온 수보다 작은 수를 지워준다. 
        while !stack.isEmpty && stack.last! < number[i] && cnt < k{ // cnt가 k 미만일 때만 지우기 실행
            stack.removeLast()
            cnt += 1 // 지운 횟수 체크
        }

        stack.append(number[i])
    }
    
    if stack.count > number.count-k { // 테스트케이스 12번 -> 반례 "4321", 1, "432" 일 경우 정답이 4321로 나와서 마지막꺼를 지워줘야함
        stack.removeLast()
    }
    
    return stack.map { String($0) }.joined()
}