백준 2331, 반복수열 swift dictionary, 거듭제곱 풀이

 

 

 

---

백준 2331, 반복수열 문제 설명

2331번: 반복수열

자세한 문제 설명은 직접 확인하고 푸시길 바랍니다.

반복수열 문제는 최근 수열 값의 각 자리수를 P번 제곱한 합을 다음 수열로 쌓아나갈때, 반복되는 수열이 발생하는데, 이때 반복되는 수열 이전의 반복되지 않았던 수열 길이를 구하는 문제입니다.

 

 

 

실버4문제입니다. 오랜만에 문제 하나 먹었습니다. 

 

 

 

 

생성되는 수열의 연산 규칙은 위 내용을 참고 바랍니다. A라는 숫자로부터 시작해서 각자리의 숫자를 P번 제곱한 합을 다음 수열 값으로 이어가면서 반복수열을 확인하고, 반복되는 수열 이전의 수열길이를 출력하면 되는 문제입니다.

수열의 반복은 swift의 해시 자료구조인 dictinoary를 사용하겠습니다. 또한 제곱의 경우 거듭제곱 알고리즘을 이용해서 O(logN)의 시간복잡도로 연산하도록 하겠습니다.
*사실 본 문제에서는 제곱을 해봐야 5번 뿐이기에 거듭제곱 알고리즘을 사용하지 않아도 되긴 합니다만.. 상기 차원으로 사용할게요!

바로 swift언어로 본 문제를 풀어보겠습니다!

 

 

 

 

---

백준 2331, 반복수열 문제 swift 풀이
dictinoary, 거듭제곱 알고리즘 활용 

먼저, A, P를 입력받았습니다. dic은 각 인덱스 값에 대한 P번 제곱했을때의 결과값이 들어갑니다. 이때 [0, 1]을 넣는 이유는 자릿값이 0, 1인 경우에는 몇번의 제곱을 해도 그대로 0, 1이기때문에 미리 넣어둘 수 있었습니다. dic2는 앞서 말했던, 수열의 반복여부를 판단하는데 사용하며, 반복되지 않은 수에 대한 인덱스값을 넣어서 반복값이 들어왔을 경우, 반복되는 시작점을 바로 알아내는데에 사용합니다.

 

 

 

 

Int 익스텐션 함수를 만들어봤습니다. 그냥 기본 클로져, 함수 등으로 구현해서 사용해도 무방합니다. 거듭제곱 알고리즘을 활용해서 O(logN)의 시간복잡도 특정 제곱 결과값을 반환해주는 메서드를 구현했습니다.

 

 

 

 

24 ~ 26행) 자릿값이 2 ~ 9 일 때에 대한 P제곱 결과값을 순차적으로 dic에 넣어줍니다. 

28 ~ 31행) value에 수열 첫번째 값인 A를 넣었습니다. cnt는 현재 수열이 몇번째 수열인지 확인하는데 사용합니다. (zero-based index) lastIdx는 그냥 없는 셈 쳐주세요. 사용하지 않네요 ㅎㅎ..

32 ~ 47행) 최근 연산한 수열 값 value에 대한 각 자리의 P제곱 합을 연산하고, 중복여부를 체크하는 로직입니다. 여기에서 중복이 발견 될 경우, 중복 수열의 시작점 이전까지 있었던 수열이 중복되지 않는 수열이죠. 
문제 설명에 나온 예제 입력을 예로 들자면, ex) 57, 74, 65, 61, 37(중복 수열값의 시작점) ..... 37(동일 값 발견 시점) => 중복 수열 시작점 이전까지의 수열이 중복되지 않은 수열입니다.

40행) 이때 중복수열값의 시작점 인덱스는 zero-based index이므로, 이를 그대로 반환하면 반복되지 않는 수열의 갯수를 구할 수 있습니다. 

 

 

 

---

오늘은 실버4 티어의 반복수열 문제를 dictionary, 거듭제곱 알고리즘 등을 활용해서 풀어봤습니다. 질문, 의견 댓글 환영합니다. 즐거운 코딩 되시길 바랍니다.

전체코드 아래 공유하겠습니다!

let ip = readLine()!.split(separator: " ").map { Int(String($0))! }
let (A, P) = (ip[0], ip[1])
var dic = [0, 1]
var dic2 = [Int: Int]()

extension Int {
    func customPow(cnt: Int) -> Int {
        var result = 1
        var cnt = cnt
        var flag = self
        while cnt > 0 {
            if cnt % 2 == 0 {
                flag *= flag
                cnt /= 2
            } else {
                result *= flag
                cnt -= 1
            }
        }
        return result
    }
}

(2...9).forEach { num in
    dic.append(num.customPow(cnt: P))
}

var value = A
var cnt = 1
var lastIdx = 0
dic2[value] = 0
while true {
    var result = 0
    while value > 0 {
        result += dic[value % 10]
        value /= 10
    }
    
    if dic2[result] != nil {
        print(dic2[result]!)
        break
    }
    
    dic2[result] = cnt
    value = result
    cnt += 1
}