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

 

아이디어는 바로 떠올랐다.

앞에서부터 현재 수와 다음 수를 비교하여 작다면 현재 수를 제거하는 식으로 풀면 될 것 같았다.   

 

Code. 1

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    
    var numAry = number.map{ String($0) }
    let numCount = number.count - k
    var i = 0
    

    while numAry.count != numCount {
        
        // 배열 끝까지 탐색하면 뒤에서부터 제거
        if i >= numAry.count-1 {
            numAry.removeLast()
        } else if numAry[i] == "9" {		// 해당 수가 9일 경우 다음으로 넘어감
            i += 1
        } else {
            if numAry[i] < numAry[i+1] {	// 현재 수가 다음 수보다 작을 경우 제거,
                numAry.remove(at: i)
                if i > 0 {			// 이전 수와 다음 수를 다시 비교하기 위해 index 조정
                    i -= 1
                }
            } else {			// 해당 없을 경우 다음 탐색 
                i += 1
            }
        }

    }
    
    return numAry.joined()
}

 

 

 

 

 

 

그런데 10번 케이스가 시간 초과가 나왔다.
여기에 이런 저런 조건들을 조정하면서 풀어보려 했는데 10번에서 걸렸다. 

다른 사람의 아이디어에서 도움받아 해결했다.

 

Code. 2

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    
    let numAry = number.map{ String($0) }
    let numCount = number.count - k
    var startIndex = 0
    var endIndex = k
    var stack = [String]()
    
    while stack.count != numCount {
        var max = "0"

        if startIndex < endIndex { 		
            for i in startIndex...endIndex {		
           	 
            	// stack에 넣을 수 있는 가능성이 있는 수들 중 최대 값을 추가한다.
				// 해당 수를 stack에 넣을 경우 그 앞의 수들은 볼필요가 없으므로 
				// startIndex를 1 추가해준다. 
                if numAry[i] == "9" {		// 최대 수가 9인경우 해당 수를 넣는다.
                    max = numAry[i]
                    startIndex = i + 1
                    break
                } else if numAry[i] > max {	
                    max = numAry[i]
                    startIndex = i + 1
                }
            }
            endIndex += 1
            stack.append(max)
        } else { 		// startIndex가 endIndex를 따라잡을 경우, 
			// 즉, 남은 stack 에 들어갈 수들이 이미 확정난 경우 
			// stack에 남은 수를 전부 추가한다.
            stack += numAry[startIndex...(numAry.count-1)]
        }
        
    }
   
    
    return stack.joined()
}