[Swift Algorithm] 프로그래머스 17687 N진수 게임 (2018 카카오 블라인드)

programmers.co.kr/learn/courses/30/lessons/17687

코딩테스트 연습 - [3차] n진수 게임

 

풀이과정

요약

0부터 차례대로 알맞는 진법에 맞게 변환해서 문자열을 계속 이어가고

이때 변환된 문자열의 길이가  t * m 를 넘어가면 비효율적이기때문에 그 전에 종료

변환한 문자열에 p의 순서에 맞게 접근해서 t개 만큼 출력

---

 

처음 접근방법에는

while문으로 돌면서 

입력받은 n(진법) 만큼의 나머지를 구해서

진법String을 구하고 

계속 더해가는 식으로 저장해놓고

저장한 String에 extension을 사용해서 접근했어요

extension String {
    
    subscript (at index: Int) -> Character {
        return self[self.index(self.startIndex, offsetBy: index)]
    }
}

 

그런데

시간 초과가 뜨더라구요?!?!

 

더 줄이는 방법이 뭐가있을까해서

알아보니

 

우선 String에 radix변환하는게 잇더라구요?

당연히 구현하는거보단 효율적이라고 생각해서 

radix함수사용으로 변경했더니..!

차이가없어요 ^____^

 

다시 더 생각해보니

string을 순서대로 더하고

마지막에 string을 반환할때 reverse를 사용했었는데

그 작업보단 거꾸로해서 스트링을 더해서 반환하면 낫겟더라구요

불필요한 계산을 제거했더니..!

차이가없어요^____^

 

튜브의 순서마다 출력하는것도 for을 돌면서 하나하나 보지않고

stride를 이용해서 접근했더니...!

차이가없어요^____^

 

 

아 그럼 도대체 이유가 뭘까...

더 줄일 수 있는 방법을 못찾겠던 중...!

extension에 string의 offset을 접근하는 작업이 오래 걸린다고하네요?!?!

지우고

배열로 만들어서 접근하는 방식으로 변경하니까 바로 통과가 됬구요

 

결과기준으로 시간차이가 최대300배는 차이났던것 같아요

문자열이 길어질수록 더 느려진다고하구요!!

 

 

 

private func solutionP17687(_ n:Int, _ t:Int, _ m:Int, _ p:Int) -> String {

    var transform: [Character] = []
    var curNum = 0
    while transform.count <= t*m {
        let change = String(curNum, radix: n, uppercase: true)
        change.forEach { transform.append($0) }
        curNum += 1
    }
    
    var result = ""
    for i in stride(from: p-1, to: transform.count, by: m) {
        result.append(transform[i])
        
        if t == result.count {
            break
        }
    }
    return result
}