백준 17103 - 골드바흐 파티션

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

17103번: 골드바흐 파티션

 

티스토리에 올려둔 골드바흐를 복습하고나서 새로운 골드바흐 문제가 있길래 시도해봤는데 시간초과가 나서 풀지 못했다.

구글링을 해보며 다른 사람의 코드를 보았는데도 이해하는데 굉장히 많은 시간이 걸렸다..

 

 

실패 코드 리뷰)

def sosu(n):  # 소수 판별 함수
    if n==0 or n==1:
        return 1
    else:
        for i in range(2, int(n**0.5)+1):
            if n%i==0:
                return 1
        return 0


t = int(input())

for i in range(t):
    cnt = 0
    n = int(input())
    for j in range(2, n//2+1):
        if sosu(j)==0 and sosu(n-j)==0:
            cnt += 1
    print(cnt)

일단 굉장히 흔한 소수 판별 함수를 구현하여 사용하였다.

반복문을 사용하여 숫자를 입력받고 그 숫자가 소수인지 판별하기 위하여 소수 판별 함수를 사용하였다.

골드바흐 파티션의 갯수를 구하기 위해 2부터 해당 숫자의 절반까지 반복문을 돌려 소수 판별함수를 호출했다.

소수 판별 함수 내부를 살펴보면, 이 함수 안에서도 반복문이 사용된다.

파이썬은 다른 언어와 달리 반복문에 취약하고, 따지고 보면 반복문 안에 반복문 안에 반복문을 사용했으니.. 당연히 시간초과가 날 수 밖에 없었다.

 

 

 

성공 코드 리뷰)

def sosu(n):  # 소수 여부 리스트 반환 함수
    result = [True] * n  # n 길이의 리스트 생성 후, 모든 숫자가 소수라고 초기화
    result[0] = False  # 0은 소수 아님
    result[1] = False  # 1도 ㅅ수 아님
    for i in range(2, int(n ** 0.5) + 1):  # 에라토스테네스의 체
        if result[i]:  # 해당 숫자가 소수일 경우
            for j in range(2 * i, n, i):  # 해당 숫자의 배수는
                result[j] = False  # 소수 아님
    return result


T = int(input())
nums = [int(input()) for i in range(T)]
m = max(nums)  # 입력받은 숫자 중에서 가장 큰 수
sosus = sosu(m)  # 소수 여부 리스트
for i in nums:
    cnt = 0  # 골드바흐 파티션의 갯수
    for j in range(2, i // 2 + 1):  # 서로 위치가 바뀌어도 같으므로 절반까지만 반복문 수행
        if sosus[j] and sosus[i - j]:  # 둘 다 소수일 경우
            cnt += 1
    print(cnt)

해당 코드에서 시간 소모를 줄일 수 있도록 하는 포인트 위주로 설명하겠다.

 

1. 해당 문제에서는 입력받을 수 있는 짝수의 크기를 1,000,000 이하로 제한하고 있다.

테스트 갯수 T개의 숫자를 입력받을텐데, 그 때마다 소수를 구할 필요가 없다.

입력받은 숫자들 중에서 가장 큰 숫자까지의 소수만 리스트에 담아두고 나서 이걸 계속 사용하면 된다.

==> m에 최대값을 담아두고 그걸 인자로 해서 함수를 호출하였다.

 

2. 소수 여부 리스트를 반환해주는 함수 내부를 살펴보자.

최대값인 n만큼의 길이를 갖는 리스트를 선언해주고 해당 숫자가 소수인지 아닌지 판별해주면 된다.

이 과정에서, 전에 공부한 에라토스테네스의 체를 사용했다.

에라토스테네스의 체란, 소수임을 판별하기 위해 모든 범위에서 나누기 하는 것이 아니라,

해당 숫자의 제곱근까지만 보면 소수임을 판별할 수 있다는 로직이다.

 

3. 에라토스테네스의 체를 사용한 반복문 안에 배수를 걸러주는 로직을 작성하였다.

소수란, 약수가 1과 자기자신 밖에 없는 수이다.

즉, 다른 수의 배수일 경우 소수가 아니다.

이를 이용하기 위해 소수일 경우, 해당 소수의 배수를 모두 소수가 아니게 판별하였다.

그럼 에라토스테네스의 체 반복문 안이 소수일 경우에만 로직이 돌아가게끔 작성을 해놔서 False이면 자동으로 그냥 스윽 넘어가게 되므로 여기서 그래도 꽤 많은 시간을 단축할 수 있다.

 

4. 골드바흐 파티션은 위치가 바뀌어도 똑같으므로 하나로 퉁치기 때문에 결국 반복문은 절반만 돌리면 된다.

(2,3 이나 3,2나 결국 같은 것)

 

 

평소 클린한 코드는 그냥 간결한 코드 작성이라고만 생각하고 메모리, 시간 소모 측면에서 거의 생각하지 않고 있었다..

앞으로는 메모리, 시간적 측면에서 더 생각해보고 효율적인 코드 작성을 위해 노력해야겠다.