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

<문제>

---

<전략짜기>

시도는.. 큰 수가 앞에 올수록 좋은것이여! 좋은게 좋은것이여! 👍 라는 판단으로 시작한다. k개를 지운다는 것은 결과를 number.count - k 자리 수로 만든다는 것이다. 주어진 number에서 등장하는 숫자를 Set으로 중복제거한 후에 정렬한다면, 등장하는 숫자들에서 큰수를 순서대로 사용할 수 있다. 그럼 가장 큰 수가 number에서 등장하는 첫번째 index를 찾고, 이 값이 결과값에 들어갈 수 있을까? (결과값의 남은 자리수보다 number에서 이값 뒤에 남은 숫자의 갯수가 많아야함)를 체크한 뒤에.. 하나씩 넣어주면 되겠군! 그리고 사용한 가장 큰 수와, number에서 처음~큰수가 존재했던 인덱스까지를 삭제해준다.(이전값은 필요도 없을뿐더러 탐색 시간만 늦춤 ㅋㅋ ) 예를들어서.. "1231234" 케이스를 생각해보면, 처음에 4를 가져오는데 이건 자릿수 조건을 충족하지 못한다. 그 다음은 3을 가져오고, 첫번째 등장하는 3이 2번인덱스에 있네?? 오케이. 그리고 남은자릿수도 아직 0이고(결과에 들어간 수가 없음) 3 뒤에 있는 숫자의 갯수도 3포함 5개니까 자릿수 조건을 만족하는군! 하고 3을 결과에 넣어준 후에, 0번~2번 인덱스 값을 지워준다. 그럼 1234가 남고 같은 과정을 반복하면, 결과를 도출할 수 있을 것이다.

👉 7~10번 케이스에서 시간초과 😭

 

시간초과가 떠서 한참 리펙토링을 고민했던 것 같다. 불필요한 정렬이나 탐색이 없는지.. 허허 그러나 아무리 뜯어고쳐대도 7~10번 시간초과 ㅋㅋ 다시 전략짜기.. stack의 개념을 활용해보자. 처음부터 그냥 되는대로 결과에 넣을거야. 다만! 조건이있어.. 이 스택의 마지막에 들어있는 수보다 지금 들어갈 수가 크니? 그럼 앞에 것을 Pop 하고 들어가면 돼. (이걸 확인하려면 일단 스택이 비어있는지 확인해야겠군?) 그리고.. 이 새로운 숫자가 들어갈때 stack의 마지막 수를 Pop해서 날렸니? 그럼 그때마다 pop한 횟수를 저장할건데.. 그 pop 한 횟수가 주어진 k보다는 크면 안되기때문이지..!! 라는 생각으로 쭉~ 돌리면 결과가 나올 것 같다!

 

<코드>

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    let number = number.map { String($0) }
    var stack: [String] = []
    var delCnt = 0
    
    for n in number {
        while !stack.isEmpty && delCnt < k && stack.last! < n {
            stack.removeLast()
            delCnt += 1
        }
        stack.append(n)
    }
    while stack.count > number.count-k {
        stack.removeLast()
    }
    
    return stack.joined()
}

 

<Lesson Learned>

솔직히 새로 알고리즘 공부를 시작하면서, 제일 오래 걸린 문제다..ㅎ 삽질과 삽질의 반복(시간초과와 예외케이스의 굴레..)으로.. 2시간은 푼 것 같다 😭 (어디 코딩테스트였으면 슈.퍼.광.탈 👊) 그래서 결국 해냈으니 다행이긴 하네 ㅋㅋ!!! 두번째 전략에서도 12번 테스트케이스를 계속 틀렸는데, 평소에는 그렇게 생각 잘하던 마지막 경계점에 대한 생각을 빠뜨렸던 것 같다. 이 알고리즘으로 생각해보면 54321 처럼 내림차순으로 정렬되어 있는 입력이 들어오면.. 뭐 거르고 pop할것도 없이 54321을 결과로 받아버린다..하하.. 그래서 마지막에 내 결과(stack)이 가능한 자릿수보다 커져버렸니? 그럼 마지막 것을 순차로 잘라! 라는 로직을 넣어줬다.. 😂 암튼 우여곡절끝에 풀어서 배운게 있어서 다행이다~~~~ 문제 풀기전에 Brute Force 생각보다는 일단 사용가능한 적절한 자료구조가 있는지 충분히 고민해보고 시작해야겠다 👍 다른사람의 풀이를 봤을때도 솔직히 이건 내가 젤 잘푼것 같다 !! 

 

 

 

출저 : 프로그래머스 큰 수 만들기