[프로그래머스] (Swift) 큰 수 만들기 (lv.2, 그리디)

🟠 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42883

프로그래머스

 

🟠 나의 풀이

가장중요한 것은 입력된 순서 그대로를 유지하고 숫자를 삭제시키는 것이었다. 무조건 작은 숫자만을 찾아서 삭제하는 것이 아니라, 입력받은 number에서 적절한 위치에 있는 숫자들을 삭제하여 가장 큰 수를 만들어내는게 핵심이었다.

여기서 내가 캐치해낸건, 먼저 K번째 수까지 비교해서 맨앞자리에 가장 적당히 큰 수가 오게 만들어주는것.

먼저 이것을 파악했다. 이렇게 하게 되면, 이 이후의 숫자들을 비교해가면서 큰 수를 뽑아주는게 아닌가? 싶었다. 코드를 어떻게 짜야할지 막막했지만 일단 막 풀이를 생각해봤다.

그리고 이것을 이제 반복문을 돌려서 찾아주어야하는데,,, 초반에 어떻게 for문을 돌려야할지 막막했다. 현재 인덱스로 선택된 친구 그 다음부터 봐야하기 대문에 currentIdx와 nextIdx를 두어서 for문을 돌려주었다. 그리고 총 6자리가 나와야하기 때문에 숫자 선택도 for문을 이용해서 6번만 해주면 될 것이라고 판단했다. 그리고 아래와 같이 생각을 하고 코드로 구현했다.

❌ 첫번째 풀이 - 테케 10 시간초과

그냥 냅다 구현했는데, 정답은 맞았지만 테케 10번 하나에서 시간초과가 났다. 뭐 때문일까 ㅠㅠ

import Foundation

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

    for i in 0..<number.count - k {
        var tempMax = -999

        for j in nextIdx...i+k {
            if tempMax < numArr[j] {
                tempMax = numArr[j]
                currentIdx = j
            }
        }

        answer.append(tempMax)
        nextIdx = currentIdx + 1
    }

    return answer.map{ String($0) }.joined()
}

일단 내가 지금 짠 코드는 O(n^2)이고, 주어지는 nubmer가장 큰 수가 100만이다. 100만x100만이 된다면, 거의 1억 가까이 되는 만큼 for문이 돌아갈 것이다. 시간초과가 나므로 시간복잡도를 O(n)으로 줄여주는 풀이가 필요해 보인다. 

미쳐돌아가네.. 시간초과......

 

✅ 두번째 풀이 - stack을 사용한 풀이 (정답코드)

인터넷을 참고했다.... stack을 사용해서 풀어보라는 의견이 많았다. 그럼 O(n)의 시간복잡도로 풀 수 있다고 했다. 내가 지금 푼 풀이를 기반으로 stack을 어떻게 사용할 것인지 머리를 굴려보았따. ... ...... .어렵네....... stack을 활용한 알고리즘을 도대체 어떻게 생각해낸거지? 다들 똑똑하다... 

도대체 stack을 활용해서 푼다는게 이해가 되지 않아서 다양한 사람들의 코드를 참고했다. stack을 활용한 풀이도 for와 while문이 중첩되는데 어느 부분에서 시간복잡도가 작은걸까?

음,, 내생각에는 일단 내 풀이는 모든 수가 이중 for문을 거치게 된다. 하지만 stack을 활용한 (아래) 풀이는 k만큼 수가 다 지워졌다면, 남은 수들을 모조리 stack에 넣어줌으로써 반복문이 돌아가는 횟수를 최소화시켰다. 아무래도 이 부분에서 시간복잡도가 조금 줄어들었기 때문에 통과할 수 있었지 않을까 싶다.

코드 설명은 주석으로 달아놨다.

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

    for i in 0..<number.count {
        // 아직 k번만큼 안지워졋고, answe가 비워져있지 않고, answer의 마지막에 있는 값이 지금 넣으려는 값보다 작으면
        // answer에 있는 마지막 값을 지워버리세요.
        while newk > 0, !answer.isEmpty, answer.last! < numArr[i] {
            answer.removeLast()
            newk -= 1
        }

        // 만약 k번만큼 전부 지웠다면
        // answer에 지금 검사하지 않은 남은 뒤에있는 numArr를 모두 넣어주세요.
        // 만약 k번만큼 전부 지우지 않았다면
        // answer에 지금의 numArr[i]를 넣어주세요.
        if newk <= 0 {
            answer.append(contentsOf: numArr[i...])
            break
        } else {
            answer.append(numArr[i])
        }
    }

    // prefix : 앞에서부터 원하는 갯수의 원소들만 출력해준다.
    // 우리는 number.count - k 자리수를 원해하기 때문에 넣어줘야한다.
    // number = 999 , k = 1 에서 answer은 [9, 9, 9]가 되기 때문에 여기서 한개만 출력해준다. prefix의 역할
    return String(answer.map{ String($0) }.joined().prefix(number.count-k))
}

 

 

 

참고 코드 - https://rldd.tistory.com/159?category=963241 

[Swift] 프로그래머스 LV2. 큰 수 만들기

참고 코드 및 풀이 -