[Google Kick Start] 2022 구글 킥스타트 Round B Palindromic Factors 풀이

 

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/00000000008caa74/0000000000acee89

Kick Start - Google’s Coding Competitions

 

나의 풀이

---

1. 약수를 구하는 함수 findFactors()를 만든다.

2. 팰린드롬인지를 판별하는 isPalindrome() 함수를 만든다.

약수를 구하기 위해선 1~int(sqrt(A))+1 만큼의 범위 동안 나누어 떨어지는 수를 찾으면 된다. 중복되는 경우가 생길 수 있으니 set에 저장한다.(예컨대, 25의 경우 5*5이므로 5가 중복으로 카운트 된다.)

팰린드롬을 판별하기 위해선 길이가 짝수, 홀수인 경우로 나누어 주면 된다.

 

코드

---

# https://codingcompetitions.withgoogle.com/kickstart/round/00000000008caa74/0000000000acee89
import math 

def findFactors(a):
    factor_set = set()
    for i in range(1, int(math.sqrt(a))+1):
        if a % i == 0:
            factor_set.add(i)
            factor_set.add(a//i)
    return factor_set

def isPalindrome(s):
    if len(s)==1:
        return True
    if len(s) % 2 == 0:
        left = s[:len(s)//2]
        right = s[len(s)//2:]
    elif len(s) % 2 == 1:
        left = s[:len(s)//2]
        right = s[len(s)//2+1:]
    if left == right[::-1]:
        return True
    return False

for i in range(int(input())):
    n = int(input())
    factors = findFactors(n)
    cnt = 0
    for f in factors:
        if isPalindrome(str(f)):
            cnt += 1
    print(f"Case #{i+1}: " + str(cnt))