programming

Smart Number 파이썬 풀이 및 해설


by Kitle · 2021. 01. 03.



해커랭크 사이트의 Smart Number 퀴즈에 대한 풀이입니다.

이번 문제도 기존 코드를 주고 디버깅 하는 문제입니다.


문제

A number is called a smart number if it has an odd number of factors. Given some numbers, find whether they are smart numbers or not.

스마트 넘버란 숫자의 팩터들의 갯수가 홀수인 것을 말한다. 어떤 숫자들이 주어졌을 때 이들이 스마트 숫자인지 아닌지를 찾아라.

숫자 팩터는 곱해서 나타날 수 있는 수이다. ex) 8이라면 1 x 8, 2 x 4 즉 두개의 쌍의 각각 순자들이 팩터가 된다. 

입력예시

4
1
2
7
169

출력 예시

YES

NO

NO

YES


설명

첫번째 입력은 테스트 케이스 숫자를 나타낸다. 위 예시에서는 1, 2, 7, 169 4개의 입력이므로 첫줄에 4가 입력되었다.
1의 인자는 1에 불과 하므로 홀수이므로 답이 YES가 된다. 2의 인자는 1과 2이다. 짝수이므로 No. 7의 인자는 1과 7이다. 정답은 NO. 169의 인자 1,13,169이다. 홀수 이므로 답은 Yes이다.

풀이

import math

def is_smart_number(num):
val = int(math.sqrt(num))
if val ** 2 == num:
return True
return False

for _ in range(int(input())):
num = int(input())
ans = is_smart_number(num)
if ans:
print("YES")
else:
print("NO")

해설

디버깅용으로 디폴트로 주어진 소스코드가 math.sqrt를 사용한다는 것을 알 수 있다. 제곱근을 가지고 추정해 응용할 수 있고 is_smart_number 를 수정하라고 했으므로 밑의 함수는 건드릴 필요가 없다.

어떤 숫자가 주어지면 팩터는 나누어 떨어지는 수로 쌍을 구할 수 있다. 하지만 예외적으로 제곱근이 주어지는 경우 홀수가 된다. 

(1,13,169) 의 경우 13 x 13 = 169 가 예외적으로 존재한다. 따라서 제곱근이 존재 여부에 따라 smart number 인지 아닌지를 알 수 있다. 다만 구해진 제곱근이 딱 나누어 떨어지지 않아도 파이썬 함수에서는 값이 나타나므로 다시 이 숫자를 가지고 제곱을 해 원래 숫자로 복원되는지 판단하는 것 까지 필요하다.

 결국 어떤 숫자가 주어지고 제곱근을 구한뒤, 이 제곱근을 제곱하여 원래의 수가 나오는지 확인하여 이게 맞는 경우는 제곱근이 존재하게 되므로 스마트 숫자라고 볼 수 있다. 


풀이 깃허브에서 보기 : https://github.com/kitlexyz/algorithm/blob/master/hackerrank/smart-number.py

원본 퀴즈 출처 : https://www.hackerrank.com/challenges/smart-number/problem