[백준] 1016번: 제곱ㄴㄴ수 - 파이썬

🔈 문제

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

 

📝입력

첫째 줄에 두 정수 min과 max가 주어진다.

 

📑출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

 

❗❗제한

- 1 ≤ min ≤ 1,000,000,000,000
- min ≤ max ≤ min + 1,000,000

 

📚 문제 풀이

제곱ㄴㄴ수는 제곱수로 나누어 떨어지지 않는 수, 예를 들어 1,2,3,5,6,7,10을 의미한다. 4와 8은 2의 제곱수 4로 나누어 떨어지기 때문에 제외 되는 것이다.

 

처음에는 후보 숫자 범위 리스트(n <= i <= m, 이때 n=min, m=max)를 만들고 제곱수 리스트를 만들어 나누어 떨어지는지 체크하는 방식으로 문제를 접근하였는데 메모리초과가 나왔다.

 

그래서 방법을 바꾸어 후보 숫자 범위 리스트의 원소로 숫자를 넣는게 아니라 배열의 인덱스를 이용하여 그 수가 제곱ㄴㄴ수인지 확인하였다.

즉 초기화를 arr = [1]*(m-n+1) 이런 식으로 하고 방문하면 0으로 값을 변경한다. 그리고 마지막에는 sum(arr)로 1의 값을 측정한다. 

 

제곱근 리스트는 2부터 m의 제곱근 까지이다. 

하나씩 제곱해준다음 배수가 n과 m범위 안에 있다면 arr 배열을 0으로 초기화 해준다.

 

 

💻 코드_1

n,m = map(int,input().split()) # min, max

sqrt_nums = [i**2 for i in range(2, int(m**0.5)+1)] # 제곱근 리스트
arr = [1]*(m-n+1) # 제곱ㄴㄴ수 확인 배열

for i in sqrt_nums:
    tmp = (n//i)*i 
    # 범위 안까지
    while tmp<=m:
    	# 범위 안이라면 0으로 초기화
        if n <= tmp and tmp <= m:
            arr[tmp-n] = 0
        tmp += i # 배수
print(sum(arr))

첫번째 정답 코드는 이렇게 나왔다. 다른 사람들과의 코드를 비교해보니 공간복잡도가 조금 많이 나오는것 같아서 제곱근 리스트를 따로 만들지 않아보았다.

 

💻 코드_2

n,m = map(int,input().split())

arr = [1]*(m-n+1)
sqr = 2
while sqr <= int(m**0.5):
    i = sqr**2
    tmp = (n//i)*i
    while tmp<=m:
        if n <= tmp and tmp <= m:
            arr[tmp-n] = 0
        tmp += i
    sqr += 1
print(sum(arr))

이렇게 하였더니 공간복잡도는 줄었지만 시간복잡도가 늘어났다. 늘어난 이유는 첫번째 while 문에 확인 연산인 sqr <= int(m**0.5) 에서 매번 m**0.5 연산을 하여 시간이 오래걸린다고 생각해 변수를 만든다음 여러번 연산하지 않게 하였더니 시간이 많이 줄었다.

 

💻 코드_3

n,m = map(int,input().split())
last = int(m**0.5)
arr = [1]*(m-n+1)
sqr = 2
while sqr <= last:
    i = sqr**2
    tmp = (n//i)*i
    while tmp<=m:
        if n <= tmp and tmp <= m:
            arr[tmp-n] = 0
        tmp += i
    sqr += 1
print(sum(arr))

 

🍭 시행착오

인간승리

 

🔗 문제링크 제곱 ㄴㄴ 수

1016번: 제곱 ㄴㄴ 수