[프로그래머스] 탐욕법(Greedy) 큰 수 만들기 with Swift

안녕하세요. 오늘은 프로그래머스 큰 수 만들기 문제를 풀어보도록 하겠습니다.

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

 

우선 탐욕(greedy) 알고리즘에 대해서 알아보겠습니다.

 

탐욕 알고리즘은 순간순간에서 local한 최적값을 선택하여 global한 최적값을 도출해나가는 알고리즘입니다.

 

하지만 알고리즘 예시에서 보듯이 완전하게 정렬되지 않은 경우(Heap)에는 최적값을 못찾는 단점이 있습니다.

 

이제 문제를 풀어보겠습니다.

 

이 문제는 한 숫자씩 최대값을 찾아서 answer에 넣어주면 되는 문제입니다.

 

첫 탐색에서는 0 ~ K 번째 까지 탐색하고 최대값은 N1 번째자리수에서 찾았을경우

두번째 탐색에서는 N1 + 1 ~ K+1까지 탐색하고 최대값은 N2번 번째자리수에서 찾았을경우

세번째 탐색에서는 N2 + 1 ~ K+2까지 탐색하고 최대값은 N2번 번째자리수에서 찾았을경우

 

이런 방식으로 n-k번 진행하여 globla 최적값을 찾아주면 문제가 해결됩니다.

func solution(_ number: String, _ k: Int) -> String {
    let numberArray = Array(number)
    var startIndex = 0
    var endIndex = k
    var max = 0 
    var answer = ""
    
    for _ in  0..<numberArray.count - k {
        var max:Character = "0"
        for i in startIndex...endIndex {
            if max < numberArray[i] {
                max = numberArray[i]
                startIndex = i + 1
            }
            if numberArray[i] == "9" {
                max = "9"
                startIndex = i + 1
                break
            }
        }
        endIndex += 1
        answer += String(max)
    }
    return answer
}

 

오늘은 여기까지입니다. 질문이 있으시면 댓글로 남겨주세요. 

 

좋은 하루 되세요.