백준 1644번 Two Pointer

서론

1644번: 소수의 연속합

투 포인터 문제입니다. 투 포인터 개념은 원래 알고 있던 개념이고 이번 문제보다는 일반적으로 부분합 문제가 더 대표적이겠지만 이번 문제를 풀면서 소수에 대한 개념이나 투포인터에 있어서 시간제한이나 메모리 제한을 한번 계산해보면서 기록해보려고 합니다.

제한 조건

• 시간제한 - 2초

시간제한은 2초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. 보통 투포인터 문제는 전체 데이터 리스트에서 시작과 끝 인덱스로 접근을 하는데 그렇다고 인덱스를 얻기 위해 for문 두 개로 돌리면 N^2이 되어 시간초과가 납니다. 여기서도 N은 최대 4,000,000이기 때문에 N^2는 2억(2초)을 훌쩍 넘깁니다. 투포인터를 사용하여야 하고 투포인터는 시작과 끝인덱스가 N까지 가는 최악의 케이스도 2N, 즉 시간복잡도는 O(N)입니다.

여기서는 고려해야 할게 하나 더 있습니다. 바로 소수 리스트를 만드는 방법입니다. 처음에는 소수를 판별할 때 sqrt(N)까지의 수로 판별하려는 수를 나누는 방법을 사용했습니다. 이렇게 되면 4,000,000을 판별하더라도 2,000까지만 하면 되니 시간이 될 줄 알았습니다. 근데 결국 N개에 대해서 다 구하게 되면 N*sqrt(N)이 되니 시간복잡도는 N^1.5 정도가 되고 실제로 제출했을 때 시간제한으로 실패했습니다.

수 한 개만 소수인지 판단할 때는 sqrt(N)까지의 수로 나눠보는 방법이 sqrt(N)으로 빠르지만, 그 수까지 해당하는 소수를 모두 찾으려면 에라토스테네스의 체를 사용해야 합니다. 에라토스테네스의 체의 시간복잡도는 O(Nlog(logN))인데 계산하는 방법은 너무 까다로워서 그냥 가장 빠르다고 알고 있으면 될 것 같습니다.

오히려 소수 리스트를 구하는 부분이 투포인터를 사용하는 부분보다 시간복잡도가 크기 때문에 이 문제의 시간복잡도는 O(Nlog(logN))이 되고 소수를 잘 구해야하는 문제가 됩니다.

• 메모리 제한 - 128MB

메모리 제한은 128MB입니다. 선언할 부분이 4,000,000개의 데이터 정도인데 파이썬 기본 정수형 타입이 28byte이니 112MB이고 메모리 제한에 딱 맞습니다. 데이터 리스트 정도 되는 크기를 더 선언하면 안 됩니다.

Two Pointer

투포인터 자체는 그렇게 어렵지 않습니다. 에라토스테네스 체가 오히려 어렵습니다. 주석으로 설명을 달아놓았습니다. 코드는 아래와 같습니다.

import sys
input = sys.stdin.readline


N = int(input())
# 0과 1은 소수가 아니기 때문에 false
prime_list = [False, False] + [True]*(N-1)
# 기본적으로 소수를 확인할 때 그 수의 제곱근까지만 나눠보면 됩니다.
for i in range(int(N**0.5)+1):
    if prime_list[i]:
        # 안나눠진 수는 내버려두고 그 수의 간격만큼의 다음수들을 지웁니다.
        for j in range(i+i, N+1, i):
            prime_list[j] = False
prime_list = [num for num in range(2, N+1) if prime_list[num] == True]

left, right = 0, 0
cnt = 0

while right <= len(prime_list):
    temp_sum = sum(prime_list[left:right])
    if temp_sum == N:
        cnt += 1
        right += 1
    elif temp_sum < N:
        right += 1
    else:
        left += 1

print(cnt)

생각