[코딩 테스트 연습(파이썬/Python)] 백준 1016번 _ 제곱 ㄴㄴ 수

https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

[문제]

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

 

[입력]

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

[출력]

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

 

[아이디어]

1) root(max)보다 작거나 같은 소수의 제곱수에 대하여 min과 max사이의 숫자들 중 조건을 만족하는 숫자를 찾자.

2) 에라토스테네스의 체의 아이디어와 유사해보인다.
(시간초과 발생 후)
3) 결국 최대 정수 개수가 100만개임을 잘 이용해야한다.
4) 3)의 이유로, 확인하려는 소수의 제곱이 일정 수보다 커지면, 해당 소수의 제곱의 배수는 딱 하나 존재할 수 있다.
(1000 이상의 소수의 경우 그 간격이 100만을 넘어가기 때문이다. 2개 존재할 수가 없다.)
5) 모든 가능한 소수를 구해놓고, 그것으로 나누어 떨어지는지 확인하는 것은 효율성을 통과할 수 없다.
6) 결국 모든 배수는 등차 간격으로 나타남을 이용해, a 보다 큰 수 중 제곱수로 나누어지는 첫 숫자를 구하고, 그로부터 해당 제곱수를 더해나가며 그 배수들을 찾는 방법을 이용한다.

7) 처음부터 (b-a+1)*[1]의 배열을 생성해놓고, 제곱수로 나누어 떨어지는 index는 0으로 변경한다.

 

# 시간초과 2
a,b = map(int, input().split())
n = int(b**(0.5))
t = set(range(2, n+1))
for i in range(2, n+1):
    if i in t:
        t -= set(range(i*2, n+1, i))
t = list(t)
def factorization(x,d): 
    i = 0 
    tmp = dict()
    while (d[i] <= x): 
        if (x % d[i] == 0) and (d[i] not in tmp): 
            tmp[d[i]] = True 
            x = x // d[i] 
        elif (x % d[i] == 0) and (d[i] in tmp):
            return False
        else: 
            i += 1
            if i == len(d): break
    return True
cnt = 0
for m in range(a, b+1):
    cnt += factorization(m, t)
print(cnt)

가능한 모든 소수를 구해놓고, factorization이라는 함수를 정의해 두 번 이상 특정 소인수가 등장하면 False를 return하도록 하였다. 로직은 문제가 없으나 시간이 너무 오래걸린다. 소수들의 집합을 생성하면 그 최대 길이가 7만이 넘기 떄문일 것이다.

a,b = map(int, input().split())
tmp = [1]*(b-a+1); i = 2
while i**(2) <= b:
    t = i**(2)
    p, q = a//t, a%t
    if q ==0:
        d = 0
    else: d = t - q
    while 0 <= d <= b-a: 
        tmp[d] = 0
        d += t
    i += 1
print(sum(tmp))

다른 사람의 아이디어를 조금 빌려 활용했다. 전체 숫자의 개수만큼의 1을 원소로 가지는 배열을 만들어놓고, 첫 수인 a를 0번 index라 생각한다. 이후 제곱수로 나누어 떨어지는 index들을 모두 0으로 바꾸는 방법이다. 이렇게 하면 반복문이 n=100만에 대해 최대 O(n)*O(n/4) 내에서 해결되며, 4의 위치에 자리할 제곱수가 커질수록 빠르게 뒤의 빅오표현이 O(1)로 수렴하는 장점이 있다.

# ?????
a,b=map(int,input().split())
n=[1]*(b-a+1)
for c in range(2,8**7):
    k=c*c
    n[-a%k::k]=[0]*(b//k-~-a//k)
print(sum(n))

다른 사람의 코드를 보는 과정에서 미친 숏코딩을 만났다;; 8**7은 그냥 통과하기 위해 필요한 숫자 중에서도 코드 길이를 줄이기 위해 억지로 넣은 숫자고, 해당 코드를 보며 새롭게 알게된 사실은 아래와 같다.

 

① 음수를 양수로 나눈 나머지를 구하면, modulo 값을 최소의 양수로 반환한다. 즉 % 연산 자체가 '나머지'가 아니라 modulo 연산의 결과였다! 예를 들어,

이런 식이다. '-a%b'라는 표현은 a가 b로 나누어 떨어질 때는 0을, 그렇지 않을 때는 해당 숫자로부터 b로 나누어 떨어지는 첫 양수가 몇 칸 떨어져 있는지(37로부터 14칸 떨어진 51이 37에서 가장 가까운 17의 배수가 된다.) 구하는데에 이를 사용할 수 있다.

 

② 리스트의 슬라이싱에도 원하는 숫자를 리스트(혹은 iterable 객체)형태로 할당할 수 있다. 예를 들어,

이런 식이다. a의 1번 인덱스부터 -3번 인덱스 전까지, 3칸 간격으로 0, 2를 할당한 코드다. 다만 이때 원본 리스트에서 변경하고자 하는 원소의 갯수의 길이와 같은 iterable 객체를 던져주어야만 해당 순서대로 할당이 가능하다.

 

③ -~- 이라는 연산 기호

솔직히 이건 좀 겉멋 같기도 하고, 검색해도 안나와서 도통 왜 있는지 모르겠지만 ~a = -a-1 을 만족하는 것 같다. 이를 이용하면 두 정수 사이에 있는 정수의 갯수를 구할 수 있다. 예를 들면 아래와 같다.

오늘도 끝이 없다는 걸 깨달은 하루,,