[Algorithm] 1일1솔 - 백준 1644 소수의 연속합 (python3)

문제링크

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

1644번: 소수의 연속합

 

문제는 일정 범위 내의 연속된 소수의 합을 찾아야하므로 에라토스테네스의 체로 소수의 리스트를 구하고, 구한 소수 리스트에서 투포인터로 그 합을 구하는 것이 포인트이다.

이 부분을 인지해서 풀이했지만, 처음에는 시간초과가 났고 투포인터 부분에서 시간복잡도 문제가 있다고 생각했다.

val = sum(tmp[left:right])에서 (O(right-left) 만큼의 공간을 만드는 시간) + (sum 함수 시간복잡도)가 소요된다. (이 부분은 감으로 고치고 풀이 통과 후에 이왜맞과 맞왜틀을 동시에 시전하며 질문해보고 호석님께 명쾌한 조언을 들어서 답답한 부분이 해소되었다.)

# 시간초과 풀이
import sys
n = int(sys.stdin.readline())
ans = 0

# 에라토스테네스의 체
def isPrime(n):
    sieve = [True] * (n+1)
    m = int(n ** 0.5)
    for i in range(2, m+1):
        if sieve[i] == True:            
            for j in range(2*i, n+1, i):                 
				sieve[j] = False
    return [i for i in range(2,n+1) if sieve[i] == True]
    
# 투포인터로 연속합 구하기
# 여기서 시간초과 났음
tmp = isPrime(n)
left, right = 0, len(tmp)
while right <= len(tmp):
    val = sum(tmp[left:right])
    if val == n:
        ans += 1
        left += 1
    elif val < n:
        left += 1
        right += 1
    else:
        right -= 1
print(ans)

그래서 문제구간의 시간복잡도를 해결해보고자 고쳐본 코드. 에라토스테네스의 체 부분 코드는 동일하고, 투포인터로 연속합 구하는 부분을 수정했다. left, right 를 둘 다 0으로 초기값을 주고, 이로써 left와 right 간 거리를 이전 코드(left=0, right=len(tmp))보다 가깝게 설정해서 O(right-left) 시간 단축해서 통과했다.

# 통과 풀이
import sys
n = int(sys.stdin.readline())
ans = 0

# 에라토스테네스의 체
def isPrime(n):
    sieve = [True] * (n+1)
    m = int(n ** 0.5)
    for i in range(2, m+1):
        if sieve[i] == True:            
            for j in range(2*i, n+1, i):                 
				sieve[j] = False
    return [i for i in range(2,n+1) if sieve[i] == True]

# 투포인터로 연속합 구하기
tmp = isPrime(n)
left, right = 0, 0  # left, right 사이 거리를 이전 코드보다 가깝게 설정해서 O(right-left) 시간 단축
while right <= len(tmp):
    val = sum(tmp[left:right])
    if val == n:
        ans += 1
        left += 1
    elif val < n:
        right += 1
    else:
        left += 1
print(ans)

근데 질문하면서 호석님께서 이 코드도 답답고구마..ㅎㅎ.. 라는 말씀을 하시면서 val을 left, right 이동할 때 같이 끌고 가라는 조언을 해주셔서 아래 코드와 같이 sum을 없애면서 val의 시간복잡도를 줄였다.

n = int(input())
ans = 0

def isPrime(n):
    sieve = [True] * (n+1)
    m = int(n ** 0.5)
    for i in range(2, m+1):
        if sieve[i] == True:           
            for j in range(2*i, n+1, i):  
                sieve[j] = False
    return [i for i in range(2, n+1) if sieve[i] == True]


tmp = isPrime(n)+[0]  # n이 소수일 때 소수 배열의 마지막까지 체크가 되게끔 tmp의 마지막에 0을 추가해줌
if tmp:  # n이 1부터 입력될 수 있고, 1은 tmp가 빈 배열이므로 이 부분 체크해서 구분
    left, right, val = 0, 0, 0  # val을 left, right 이동할 때 같이 끌고가면서 sum 시간단축
    while right <= len(tmp):
        if val == n:
            ans += 1
            val -= tmp[left]
            left += 1

        elif val < n:
            val += tmp[right-1]
            right += 1

        else:   # val > n
            val -= tmp[left]
            left += 1
    print(ans)
else:
    print(0)

 

근데 뭔가 인덱스 마지막까지 가지 않는다고 tmp 마지막에 0을 추가해준 게 야매같아서 다시 알고리즘방에 질문ㄱㄱ

호석님이 while문 때문에 어려웠던 0을 없애는 방법을 같이 고민해주시고 코드를 공유해주셨다. 다음은 호석님이 공유해주신 코드. 

while 문의 변경과 break문의 추가가 있는 것만 달라졌지만 일단 조건문 순서 다르게 한 부분도 이상 없어서 나중에 참고하고자 그대로 올려둔다.

n = int(input())
ans = 0
def isPrime(n):
    sieve = [True] * (n+1)
    m = int(n ** 0.5)
    for i in range(2, m+1):
        if sieve[i] == True:            
            for j in range(2*i, n+1, i):  
                sieve[j] = False
    return [i for i in range(2, n+1) if sieve[i] == True]
tmp = isPrime(n)
left, right, val = 0, 0, 0
while True:
    if val < n:
        if right == len(tmp): break
        val += tmp[right]
        right += 1
    else:
        val -= tmp[left]
        left += 1
    
    if val == n:
        ans += 1
        val -= tmp[left]
        left += 1
print(ans)

 

아래처럼 이전에 tmp에 0 추가해서 통과한 코드의 투포인터 부분의 조건문 순서와 동일하게 해도 통과된다.

n = int(input())
ans = 0
def isPrime(n):
    sieve = [True] * (n+1)
    m = int(n ** 0.5)
    for i in range(2, m+1):
        if sieve[i] == True:            
            for j in range(2*i, n+1, i):  
                sieve[j] = False
    return [i for i in range(2, n+1) if sieve[i] == True]
tmp = isPrime(n)
left, right, val = 0, 0, 0
while True:
    if val == n:
        ans += 1
        val -= tmp[left]
        left += 1
        
    elif val < n:
        if right == len(tmp): break
        val += tmp[right]
        right += 1
    else:
        val -= tmp[left]
        left += 1
    
    
print(ans)

 

+덧
호석님의 투포인터 강의자료

GitHub - rhs0266/FastCampus: Fast Campus 강의 관련 자료입니다.