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

🚫  처음 접근법

문제 풀이 아이디어

저의 고질병(?)인 무조건 구현, 무조건 완전탐색으로 구현한 코드입니다. 물론 구현하면서도 Int ↔  String 연산도 엄청나게 많고 O(N * k) = O(N^2)의 시간복잡도를 가지고 있기 때문에 아마 안되겠지라고 생각하고 구현했고 실제로 안풀립니다😭

하지만 코드에 String.Index를 활용하는 방법이 있으므로 그것을 소개하고자 포스팅을 합니다.

코드

import Foundation

func highesWhenRemovedOne(_ number: String) -> String {
    var result = 0
    
    for i in 0..<number.count {
        var removed = number
        let index = number.index(number.startIndex, offsetBy: i)
        removed.remove(at: index)
        result = max(Int(removed)!, result)
    }
    
    return String(result)
}

func solution(_ number:String, _ k:Int) -> String {
    
    var result = number
    
    for _ in 0..<k {
        result = highesWhenRemovedOne(result)
    }
    
    return result
}

String.Index 사용하는 법

Swift에서는 String 타입은 Array처럼 subscript 안에서 Int를 사용할 수 없습니다. 대신에 String.Index라는 것을 사용해야 하는데요.

먼저 위 코드에서 사용한 특정 index의 Character를 제거하는 방법입니다. 먼저 String의 index() 메소드를 통해서 String.Index의 인스턴스를 구합니다. String.Index는 기본적으로 startIndex에서 시작해서 얼마나 떨어져 있는지로 정의합니다. 따라서 i번째 index를 구할 때는 아래와 예시와 같이 정의해야 합니다.

이렇게 구한 index를 활용해서 remove 메소드를 사용하면 됩니다.

let index = number.index(number.startIndex, offsetBy: i)
removed.remove(at: index)

그렇다면 다음은 특정 range의 문자열만 반환하는 것을 구현해봅니다. 1 ~ 3 index까지 반환하는 방법입니다. 일단 String.Index를 구했으면 subscript 안에서 사용하면 됩니다.

let string = "abcde"
let fromIndex = string.index(string.startIndex, offsetBy: 1)
let toIndex = string.index(string.startIndex, offsetBy: 3 + 1)
print(string[fromIndex..<toIndex])

//🖨 bcd

Stack을 활용한 풀이

포스팅이 잠시 삼천포로 빠졌습니다. 다시 돌아와서 해당 문제를 풀어보도록 하겠습니다.

문제 풀이 아이디어

주어진 숫자의 순서를 변경할 수는 없습니다. 하지만 중간에 있는 수를 제거할 수 있기 때문에 특정 숫자를 제거해서 가장 큰 수를 만들어야 합니다. 가장 큰 수를 만들기 위해서는 가장 큰 숫자가 가장 앞에 (= 높은 자릿수)에 가 있어야 합니다.

따라서 한마디로 정리하면 k개의 숫자를 제거해서 수의 앞쪽 (= 높은 자릿수)를 내림차순으로 정렬해야 합니다.

Stack을 통해서 내림차순으로 정렬하기

입력으로 들어온 수가 stack의 last보다 작다면 stack에 push하고 last보다 크다면 pop하게 되는 경우 stack 안은 내림차순으로 정렬되게 됩니다.

현재 문제를 해결하는데 적합한 방법입니다. k 만큼만 pop해서 정렬하고 나머지는 그대로 쓰는 경우 k개의 숫자를 제거한 가장 큰 수가 되기 때문입니다.

두 가지 case

Stack을 활용해서 내림차순으로 정렬할 때 k 번에 한정되어서 있기 때문에 아래 2가지 케이스가 발생할 수 있습니다.

1. stack.last와 모든 수를 비교하기 전에 k 번의 pop 횟수가 소진된 경우

이렇게 된 경우에는 숫자를 제거해서 큰 수를 만들 수 없는 상황입니다. 그냥 나머지 숫자를 stack의 마지막에 모두 넣어주면 됩니다.

2. 모든 수를 비교한 이후에도 k번의 pop 횟수가 소진되지 않은 경우

이렇게 된 경우에는 stack 안의 숫자들은 이미 내림차순으로 정렬된 상태입니다. 따라서 stack 안에 마지막 원소들을 남은 pop 횟수만큼 제거해주면 됩니다.

문제 풀이 아이디어

func solution(_ number:String, _ k:Int) -> String {
    let nums = number.map { Int(String($0))! }
    var stack = [Int]()
    var cnt = k
    
    // 모든 숫자를 순회하면서 stack을 통해 큰 수의 순서대로 정렬
    for num in nums {
        // case 1: 모든 숫자를 순회하기 전에 cnt가 0이 된 경우
        if cnt == 0 {
            stack.append(num) //👉 남은 숫자를 그냥 stack에 넣는다.
            continue
        }
        
        // stack의 마지막과 비교하면서
            // stack의 마지막 보다 크면 stack을 pop
            // stack이 비었거나 마지막 보다 작으면 push (or cnt가 0 보다 작으면)
        while true {
            if let last = stack.last, last < num, cnt > 0 {
                stack.removeLast()
                cnt -= 1
            } else {
                stack.append(num)
                break
            }
        }
    }
    
    // case 2: 모든 숫자를 순회했는데도 cnt가 0보다 큰 경우
    if cnt > 0 {
        stack.removeLast(cnt) //👉 stack에 내림차순으로 정렬되어 있으므로 마지막 cnt개를 제거한다.
    }
    
    return stack.reduce("") { $0 + "\($1)" }
}