그리디_프로그래머스_큰 수 만들기

https://programmers.co.kr/learn/courses/30/lessons/42883?language=swift 

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

 

문제 접근

하나씩 빼면서 제일 큰 경우를 sol에 저장해서 k번 반복하려고 했으나,,,

test case실패 및 time over

실패 코드

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    let arr = number.map { String($0)}
    var sol = 0
    
    for j in 0..<k {
        var temp : [String] = []
        if j == 0 {
            temp = arr
        } else {
            temp = String(sol).map { String($0)}
        }
        
        for i in 0..<temp.count {
            var tmp = temp
            tmp.remove(at:i)
            guard let num = Int(tmp.joined()) else {
                continue
            }
            
            if i == 0 {
                sol = num
            } else if num > sol {
                sol = num
            }
        } 
        
    }
    
    
    return String(sol)
}

2일차

접근 방법

이전에는 하나씩 뺀 경우를 비교했다면, 다른 이의 접근방법을 참고하여, i, i+1인덱스의 숫자를 비교해서 진행했다.

실패 코드

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    var arr = number.map { String($0)}
    var sol = 0
    var skipCounter = 0
    
    for j in 0..<k {
        if arr.first! == "0" {
            arr.removeFirst()
            continue
        }
        
        if skipCounter > arr.count-1 {
            skipCounter = arr.count-2
        }
        if skipCounter < 0 {
            skipCounter = 0
        }
        
        for i in skipCounter..<arr.count - 1 {
            if Int(arr[i])! < Int(arr[i+1])! {
                arr.remove(at:i)
                skipCounter = i - 1
                break
            }
            
            if i == arr.count - 2 {
                arr.remove(at: i+1)
            }
        }
    }
    
    
    return arr.joined()
}

결과

테스트 케이스 결과

테스트 1 〉	통과 (0.07ms, 16.2MB)
테스트 2 〉	통과 (0.07ms, 16.2MB)
테스트 3 〉	통과 (0.14ms, 16.6MB)
테스트 4 〉	통과 (0.30ms, 16.5MB)
테스트 5 〉	통과 (0.76ms, 16.4MB)
테스트 6 〉	통과 (36.09ms, 16.5MB)
테스트 7 〉	통과 (194.12ms, 16.8MB)
테스트 8 〉	통과 (1874.52ms, 16.9MB)
테스트 9 〉	통과 (138.72ms, 21MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	통과 (0.06ms, 16.3MB)
테스트 12 〉	통과 (0.06ms, 16.2MB)

몇몇 케이스에 많은 시간 소요가 발생한다.

또 다른 이의 접근 방법을 확인했는데, stack으로 풀 경우 매우 효율적으로 해결 가능하다고 한다.

내 코드에서는 remove(at) 혹은 first에서 배열의 변형이 발생하므로, 많은 자원적 소모가 있을것으로 생각한다. ( 반복문은 당연히 사용하겠지..?, 하지만 이중 반복문도 해결 가능한 것일까?)

 

해당 문제는 3일차도 계속된다....

 

21.12.01

한참 지나 다시 풀어보았다.

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    var arr = number.map { Int(String($0))!}
    
    for j in 0..<k {
        if arr.first == nil {
            break
        }
        
        if arr.first! == 0 {
            arr.removeFirst()
            continue
        }
        
        for (index, element) in arr.enumerated() {
            if index + 1 >= arr.count {
                // print("index error")
                arr.removeLast()
                break
            }
            
            if element < arr[index + 1] {
                // print("index: \(index) is removed. \(element) \(arr[index])")
                arr.remove(at: index)
                break
            } 
        }
    }
    let sol = arr.map({String($0)})
    
    return sol.joined()
}

조금 더 깔끔히 짜기는 했지만, 해당 포스트를 다시 보기 전 까지, 

stack을 사용한다는 생각을 하지 못했다. 심지어 쓰고도 못 풀었다.

 

stack이라는 힌트를 알고도 못 푼 코드

import Foundation
import Dispatch

func solution(_ number:String, _ k:Int) -> String {
    var arr = number.reversed().map { Int(String($0))!}
    var stack = [Int]()
    
    while stack.count != number.count - k {
        if arr.isEmpty == true {
            break
        }
        
        if arr.count + stack.count <= number.count - k {
            stack.append(contentsOf: arr.reversed().map({$0}))
            break
        }
        
        let first = arr.removeLast()
        
        if first == 0 {
            continue
        }
        
        if stack.isEmpty == true {
            stack.append(first)
            continue
        }
        
        if stack.last! < first {
            stack[stack.endIndex - 1] = first
            continue
        } else {
            stack.append(first)
            continue
        }
        
    }
    
    while stack.count > number.count - k {
        stack.remove(at: stack.firstIndex(where: {
            $0 == stack.min()
        })!)
    }
    
    var sol = stack.map({String($0)})
    
    return sol.joined()
}

이제는 최선을 다 한것 같으므로, 이 후는 고수의 코드를 참조한다.

 

고수의 풀이 참조

고수의 의식의 흐름을 읽고 와서, 재창조한 로직, 입력 testCase는  number: "4177252841", k: 4

1. 위 number.count - k = 6이다. 최종적으로 return될 문자열의 길이임.
2. 첫번째 숫자를 뽑을 때, 뽑힌 숫자 외의 5개의 숫자가 더 필요하므로, 뒤에서부터 5개의 숫자는 제외하고(52841) 나머지(41772) 중 가장 큰 숫자를 뽑는다(7), 제외한 숫자의 갯수를 카운트한다(+2)
3. 뽑힌 숫자(7)의 앞부분(41)을 제외하고, 남은 숫자(7252841)중 4개의 숫자를 제외하고 (2841) 나머지 중(725) .max()하여 뽑는다. (7)
4. 252841 중 뒤의 3개숫자를 제외하고(841) 남은숫자(252)중 max를 뽑는다, 이 중 앞부분은 버린다.(5) 버린숫자.count  += 1
5. 2841중 뒤의 2개를 제외하고, max를 뽑는다(8) 앞 부분은 버린다(2) 버린숫자 += 1 하여 k와 같아진다. 반복을 종료한다. 이 떄 반복을 종료하는 조건은 2가지로 한다. 버린숫자.count == k ||  남은숫자열.count + 뽑은숫자열.count == number.count - k
   • 반복 종료 조건이 두 가지인 이유는 k 가 작거나,
   • number.count - k 가 작은 case를 빠르게 완료시키기 위함.
6. 남은 41을 뽑은 숫자 뒤에 붙여서 return한다.

 

개선 코드

import Foundation
import Dispatch

func solution(_ number:String, _ k:Int) -> String {
    var arr = number.map { Int(String($0))!}
    var stack = [Int]()
    var removeCount = 0
    
    let targetNumberCount = number.count - k
    
    while !(removeCount == k || stack.count >= targetNumberCount) {
        
        if arr.isEmpty == true {
            break
        }
        
        let excludingCorrection = targetNumberCount - 1 - stack.count
        
        let corrctedEndIndex = arr.index(arr.endIndex, offsetBy: -excludingCorrection)
        
        let targetClosedRange = arr[arr.startIndex..<corrctedEndIndex]
        guard let max = targetClosedRange.max() else {
            arr.removeFirst()
            continue
        }
        
        guard let maxNumIndex = arr.firstIndex(of: max) else {
            arr.removeFirst()
            continue
        }
        
        let removeRange = arr.startIndex...maxNumIndex
        
        arr.removeSubrange(removeRange)
        removeCount += removeRange.count - 1
        stack.append(max)
        
        if removeCount == k || arr.count + stack.count <= targetNumberCount {
            stack.append(contentsOf: arr)
            break
        }
    }
    
    var sol = stack.map({String($0)})
    
    return sol.joined()
}

결과

이전 2일차 보다 성능이 나빠졌다. 성능의 개선을 위해 arr의 수정 및 removeCount를 세기를 포기한다

• 참고한 고수의 코드가 그렇다..
• 이는 arr의 수정에 의해 발생한 성능 저하로 생각된다.

테스트 1 〉	통과 (0.17ms, 16.4MB)
테스트 2 〉	통과 (0.20ms, 16.6MB)
테스트 3 〉	통과 (0.27ms, 16.5MB)
테스트 4 〉	통과 (0.71ms, 16.8MB)
테스트 5 〉	통과 (1.86ms, 16.6MB)
테스트 6 〉	통과 (464.84ms, 16.8MB)
테스트 7 〉	통과 (1273.03ms, 17.7MB)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	통과 (214.87ms, 25.5MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	통과 (0.17ms, 16.6MB)
테스트 12 〉	통과 (0.16ms, 16.6MB)

 

고수 참조 풀이의 개선

arr의 변형을 하지 않는다.

-> arr[startIndex...로직에 따른 endIndex]와 같은 방법을 사용한다.

반복 종료 조건을 closedRange의 startIndex와 endIndex가 같을 때로 정한다.

 

func solution(_ number:String, _ k:Int) -> String {
    var arr = number.map { Int(String($0))!}
    var stack = [Int]()
    
    var startIndexCorrection = 0
    let targetNumberCount = number.count - k
    
    while stack.count < targetNumberCount {
        
        if arr.isEmpty == true {
            break
        }
        
        let excludingCorrection = targetNumberCount - stack.count - 1
        
        let corrctedEndIndex = arr.index(arr.endIndex, offsetBy: -excludingCorrection - 1)
        
        
        let targetClosedRange = arr[startIndexCorrection...corrctedEndIndex]
        
        guard let max = targetClosedRange.max() else {
            break
        }
        
        guard let maxNumIndex = targetClosedRange.firstIndex(of: max) else {
            break
        }
        
        
        startIndexCorrection = maxNumIndex + 1
        stack.append(max)
        
        if startIndexCorrection == corrctedEndIndex {
            stack.append(contentsOf: arr[(corrctedEndIndex + 1)..<arr.endIndex])
            break
        }
    }
    
    var sol = stack.map({String($0)})
    
    return sol.joined()
}

테스트 1 〉	통과 (0.12ms, 16.4MB)
테스트 2 〉	통과 (0.15ms, 16.6MB)
테스트 3 〉	통과 (0.21ms, 16.5MB)
테스트 4 〉	통과 (0.62ms, 16.7MB)
테스트 5 〉	통과 (2.13ms, 16.3MB)
테스트 6 〉	통과 (463.45ms, 16.6MB)
테스트 7 〉	통과 (1090.71ms, 16.8MB)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (155.17ms, 25.1MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	통과 (0.10ms, 16.6MB)
테스트 12 〉	실패 (0.11ms, 16.3MB)

.... 좌절감이 느껴진다.

이렇게 된 이상, 고수의 알고리즘 코드를 클론코딩한다!

 

클론 코딩

나만의 맛을 추가하고 싶었는데,,,, 추가하기 정말 애매하다,,,,

아래의 코드는 몇 번 반복해서 써보며, 익힌 후 작성한 코드이다.

원문과는 정말 별 것 아닌 부분만 바뀐 거의 똑같은 코드.

 

간단한 해설과 코드

func solution(_ number:String, _ k:Int) -> String {
    var arr = number.map { String($0) } // Array(number) 만을 사용하면 Array<Character>가 된다. 이는 stack.last! < arr[i]를 사용 할 수 없게 함.
    var removeCount = 0 // 제거한 요소를 count 하는 변수
    var stack = Array<String>() //정답이 될 요소들이 들어가는 stack
    
    for i in 0..<number.count { // 각 글자에 대하여 반복함.
        while removeCount < k && !stack.isEmpty && stack.last! < arr[i] {
        
        // while 조건을 쉽게 이해하고 싶은 사람들을 위한 3줄 요약
        // 1. 지운 숫자의 갯수가 k 보다 작을 것
        // 2. stack이 empty가 아닐 것
        // 3. stack.last!가 arr[i] 보다 작을 것.
        
            stack.removeLast()  // 스택의 마지막 요소가 arr[i]보다 작으니 지운다. 아래에서 arr[i]를 추가하며 더 큰 수를 만들기 위함.
            removeCount += 1 //지웠으니까 count를 하나 늘린다.
        }
        
        if removeCount >= k { // 사실 부등호는 의미 없다고 생각한다. 등호로 작성해도 문제없이 작동 할 것이며, 실제 문제 제출과 테스트케이스에서도 문제없이 작동했다.
            stack.append(contentsOf: arr[i...]) //이미 지울 수 있는 횟수를 모두 사용했으므로, 나머지는 지울 수 없으므로, 모두 stack에 들어가는 것.
            break // 반복을 통해 뒤에 사용되야할 i...endIndex까지를 바로 위의 코드에서 모두 stack.append 했으므로, for문을 break한다.
        } else { // 지울 수 있는 횟수가 남아있으므로, while문이 arr[i+1]을 대상으로 작동 할 수 있다.
            stack.append(arr[i])
        }
    }
    
    return String(stack.joined().prefix(number.count - k)) //prefix하면 type: SubString이므로, String으로 변환한다.
    // number.count - k 는 주어진 string의 갯수에서 뺄 수 있는 횟수인 k를 빼낸 수. 최종으로 나와야 할 글자의 수다.
}

 

성능 

테스트 1 〉	통과 (0.12ms, 16.7MB)
테스트 2 〉	통과 (0.13ms, 16.6MB)
테스트 3 〉	통과 (0.16ms, 16.3MB)
테스트 4 〉	통과 (0.31ms, 16.4MB)
테스트 5 〉	통과 (0.47ms, 16.7MB)
테스트 6 〉	통과 (6.57ms, 16.8MB)
테스트 7 〉	통과 (15.45ms, 16.9MB)
테스트 8 〉	통과 (38.28ms, 18MB)
테스트 9 〉	통과 (54.33ms, 25.7MB)
테스트 10 〉	통과 (212.54ms, 27.9MB)
테스트 11 〉	통과 (0.09ms, 16.2MB)
테스트 12 〉	통과 (0.06ms, 16.5MB)

 

회고

WorkDay로만 4일 정도 들어간 알고리즘 문제.

로직이 좀 구린내가 날 지라도, 정상 작동하지만, 성능면에서 너무 나빠서 몇번이고 시도했던 문제였다.

자력으로 풀지 못한점에서 너무 아쉽다.

 

나의 마지막 코드와 고수의 코드의 차이는

max(), firstIndex(where:) 로 인한 배열 내 순회가 영향을 끼쳤다고 생각한다.

배열의 순회를 최소화하는 것이 퍼포먼스에 많은 영향을 끼친다는 것을 다시 한 번 느끼게 해 준 문제에 감사!