[Swift] 프로그래머스 | 코딩테스트 연습 -> 탐욕법(Greedy) -> 큰 수 만들기

고치기 전 코드

func solution(_ number:String, _ k:Int) -> String {
    var numberArr = number.map{ String($0) }
    var 자릿수 = numberArr.count - k
    var res: String = ""
    var n: String

    while 자릿수 > 0 {
    
        n = numberArr.prefix(numberArr.count - 자릿수 + 1).max()!
        res += n
        자릿수 -= 1
    
        for i in 0...numberArr.count - 자릿수 {
            if n == numberArr[i] {
                numberArr.removeSubrange(0..<i + 1)
                break
            }
        }
    }
    return res
}

우선, 내가 푼 방법은

만약에 7자리숫자인 1231234가 들어오고, k는 3이라고 한다면,

최종적인 res는 4자리 숫자가 되어야 한다.

 

최종 4자리 숫자 중, 가장 높은 자릿수부터 고른다. 먼저, 천의자리 숫자를 고른다.

1231234 뒤에 빨간자리는 고정시키고, 파란자리들 중 가장 큰 수를 찾는다.

그러면 1231234 이 된다. 

 

천의자리숫자는 3으로 정해졌다. 그 다음으로, 백의자리 숫자를 고른다.

앞서 한것과 마찬가지로 풀이한다.

이미 정해진 숫자보다 앞쪽에 있는 숫자는 필요없으므로 지운다.

1231234 파란자리들 중 가장 큰 수를 찾는다. 그러면 1231234 이 된다.

 

천의자리, 백의자리숫자가 각각 3,2로 정해졌다. 십의자리숫자를 고른다.

1231234 파란자리가 한자리뿐이므로 3으로 정해진다.

일의자리숫자도 마찬가지이다.

 

이렇게 3234라는 숫자가 최종적으로 나오게 된다.

 

하지만, 위의 코드는 시간초과가 떴다.

 

그래서 찾아보니,

kdgt-programmer.tistory.com/4

[프로그래머스] 큰 수 만들기 - 그리디 greedy | 스택 Stack (python) (1)

kdgt-programmer.tistory.com/5?category=1121942

[프로그래머스] 큰 수 만들기 - 그리디 greedy | 스택 Stack (python) (2)

똑같은 문제를 겪은 분이 계셨다.

 

효율적인 알고리즘을 구상하는 능력을 더 키워야겠다.

심지어 나는 스택을 사용할 생각을 해보지도 못했다. 생각의 폭이 좁았다.

연습을 더 해야겠다.

 

geonlee.tistory.com/131

[프로그래머스] 🔢 큰 수 만들기 / python

 

고친 후 코드

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    let numberArr = Array(number)
    var stack = [ numberArr[0] ]
    var count = 0
    var res: String = ""

    for i in 1..<numberArr.count {
        if count == k{
            stack += numberArr[i..<numberArr.count]
            break
        }
        stack.append(numberArr[i])
        var last = stack.count - 1
        if stack[last - 1] < stack[last] {
//            print("@stack: \(stack),     i: \(i),    last: \(last)")
            while stack.count != 1 && stack[last - 1] < stack[last] && count < k {
                stack.swapAt(last, last - 1)
//                print("@@stack: \(stack),     i: \(i),    last: \(last)")
                stack.removeLast()
//                print("#stack: \(stack),     i: \(i),    last: \(last)")
                last = stack.count - 1
                count += 1
//                print("##stack: \(stack),     i: \(i),    last: \(last)")
            }
        }
    }
    res += stack[0..<(numberArr.count - k)]
    return res
}

array의 요소 여러개를 한번에 더할때 양쪽 끝을 안써도 된다. 파이썬의 slicing처럼 그냥 [...끝] 아니면 [처음...] 이렇게 써도 된다.