프로그래머스 Lv. 2 Swift 알고리즘 - 큰 수 만들기

문제 유형이 Greedy라고 나와있어서 아.. 이게 그리디구나 싶었다..

좀 더 명확하게 하기 위해 개념을 찾아보니

'매 순간마다 최선의 경우를 고르고 다른 경우는 고려하지 않는' 알고리즘이라고 한다.

참고한 블로그에도 나와있지만 그리디의 가장 큰 문제는 최적의 해를 구하기 어렵다는 것이다.

어떤 주어진 상황에서 최고의 결과를 내기 위함이기 때문에, 그 주어진 상황이라는 것이 바뀔 때마다 최적의 해도 바뀐다.

즉, 반례 혹은 특별한 상황에 대한 대비가 되어야 한다.

(참고: https://dev-mandos.tistory.com/80)

 

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. 결국 가장 중요한 것은 앞자리이다.
2. 내가 사용할 수 있는 count(k) 안에서 가장 앞자리에  큰 수를 올리고 그 다음으로 오는 숫자들도 크기 순으로 올려준다.
3. 그래서 stack의 특징을 차용하여 ans 배열을 만들고
4. ans에 하나씩 원소를 담은 뒤 각 원소마다 값을 비교하여 들어와 있는 원소가 들어올 원소에 비해 값이 작으면 삭제해주는 것을 반복한다.
5. 이렇게 삭제가 k번 만큼 일어났을 때 함수를 종료한다.

 

 

* 코드

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    let arrNumber: [Character] = Array(number)
    var count = k
    var ans: [Character] = []
    
    for i in arrNumber {
        
        while !ans.isEmpty && count > 0 &&
        ans.last!.wholeNumberValue! < i.wholeNumberValue! {
            ans.removeLast()
            count -= 1
        }
        
        if ans.count < arrNumber.count - k {
            ans.append(i)
        }
    }
    return String(ans)
}

 

 

정리(Today I Learned)

1. String의 경우 Int를 써주면 쉽게 타입을 변환시킬 수 있다. 하지만 Character의 경우 Int로 감싸도 타입이 변환되지 않는다. 그 때 쓰는 것이 wholeNumberValue이다. 이 메서드의 경우 단순히 "4"라는 Character를 숫자 4로 바꾸는 것 뿐만 아니라, 한자로 표기되거나 기호로 표기된 숫자들도 전부 Int 타입으로 전환해준다.