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] }
}