n진수 게임

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

 

(1) 0, 1, 2, 3, ... 각각을 n진수로 변환시키고, 

(2) "0", "1", "1", "0", "1", "1" ... 이렇게 쭉 하나의 배열로(arr) 만들고,

(3) 그 문자열에서 p - 1번째, p - 1 + m 번째, 그리고 p - 1 + 2*m 번째, ... 의 인덱스의 문자들을 총 t개 뽑으면 된다.

 

 

튜브가 t번째 숫자를 말할 때는

p + (t-1) * m

번째 턴까지 필요하다.

 

 

틀린 코드 

 

이때, arr을 배열이 아닌, 하나의 문자열로 만들고, String.index 를 사용하게 되면 시간초과가 날 수 있다.

index(_:offsetBy:)는 공식문서에 나와있듯이 O(1)이 아니라 O(n)이다.

O(n), where n is the absolute value of distance.

 

O(t^2 * m)

 

stride 마다, O(p -1), O(p - 1 + m), O(p - 1 + 2m), ...O(p - 1 + (t-1)m) 이므로

등차수열의합에 따라 O(t*tm) = O(t^2 * m) 

func solution(_ n:Int, _ t:Int, _ m:Int, _ p:Int) -> String {
    let needed = p + (t - 1) * m
    var arr = ""
    var num = 0
    while arr.count < needed {	// O(t*m)
        arr += String(num, radix: n).uppercased()
        num += 1
    }
    
    var ret = ""
    for i in stride(from: p - 1, to: arr.count, by: m) {	// O(t^2 * m)
        let idx = arr.index(arr.startIndex, offsetBy: i)
        ret.append(arr[idx])
        if ret.count == t { break }
    }
    return ret
}

 

 

 

올바른 코드

따라서, [Character]나 [String]을 사용해야 O(1 * tm)로 풀 수 있다.

 

O(tm)

func solution(_ n:Int, _ t:Int, _ m:Int, _ p:Int) -> String {
    let needed = p + (t - 1) * m    // 필요한 문자열의 길이
    
    var arr: [Character] = []
    var num = 0
    while arr.count < needed {	// O(t * m)
        arr += String(num, radix: n).uppercased()
        num += 1
    }
    
    var ret = ""
    for i in stride(from: p - 1, to: arr.count, by: m) {	// O(t)
        ret.append(arr[i])
        if ret.count == t { break }
    }
    return ret
}

// O(tm + t) = O(tm)

 

 

리팩토링 코드

arr을 [String]으로 만들고, reduce를 사용해서 코드를 간결화하였다.

 

O(tm)

func solution(_ n:Int, _ t:Int, _ m:Int, _ p:Int) -> String {
    let needed = p + (t - 1) * m    // 필요한 문자열의 길이
    
    var arr = [String]()
    var num = 0
    while arr.count < needed {	// O(tm)
        arr += String(num, radix: n).compactMap { String($0).uppercased() }
        num += 1
    }
    
    // O(t)
    return stride(from: p - 1, to: needed, by: m).reduce("") { $0 + arr[$1] }
}