자연수 배열 중 원소의 합이 S인 경우를 찾을 때, $O(n)$으로 해결한다.

투포인터, 두 포인터, caterpillar method(??) 으로 불리는 알고리즘이다.

[BOJ 2003] 수 들의 합2
기본적으로 완전탐색을 통해 $O(n^2)$으로 해결할 수 있다. 하지만 시간제한이 0.5초이므로 통과할 수 없다.

투포인터 도입

그림과 같은 배열에서 합 12가 되는 지점이 있는지 찾아보자. 보다시피 $a_2$부터 $a_4$까지의 합이 존재하므로 TRUE이다.
그렇다면 매번 $i, j$마다 $a_i+..+a_j$를 계산해햐할까?
$a_0+a_1=8$이고, $a_0+a_1+a_2=15$이므로 그 뒤로 $j$를 더이상 진전할 필요가 없다. (따라서 배열의 원소는 자연수여야 한다.)
애벌레가 꿈틀거리듯이 $a_0$는 제외하면 $a_1+a_2=9$이다. 12보다 작으므로 앞으로 전진한다
$a_1+a_2+a_3=13$이므로 $12$보다 크다.
다시 $a_1$을 제외하면 $a_2+a_3=11$이다. $12$보다 작으므로 전진한다.
$a_2+a_3+a_4=12$이므로 TRUE이다.
만약 숫자가 크다 해도 애벌레의 꼬리가 머리를 추월해서는 안된다.

def solution(A, S):
    n = len(A)
    front, total = 0, 0
    for back in range(n):
        while (front < n and total + A[front] <= S):
            total += A[front]
            front += 1
        
        if total == S:
            return True
        
        total -= A[back]

start, end가 한번씩 배열을 훑으므로 $O(2n)=O(n)$이다.

[BOJ 2003] 수 들의 합2

예제 코드에서 if total == S일 때 count += 1을 해주면 된다.

[BOJ 1644] 소수의 연속합

<에라토스테네스의 체>를 이용하여 빠르게 소수를 판별하고 소수들을 배열에 저장한다. 그 이후는 예제와 동일하다.

N = int(input())
prime_list = []
is_prime = [True] * (N + 1)

# <에라토스테네스의 체>를 이용하여 소수 판별
M = int(N ** 0.5) + 1
for i in range(2, M):
    if is_prime[i]:
        for j in range(i + i, N + 1, i):
            is_prime[j] = False

# 소수인 것들만 배열에 저장
for i in range(2, N + 1):
    if is_prime[i]:
        prime_list.append(i)


# 투 포인터 알고리즘을 이용하여 구간합을 구한다.
L, R, total = 0, 0, 0
ans = 0
while(L < len(prime_list)):
    if total > N or R == len(prime_list):
        total -= prime_list[L]
        L += 1
    else:
        total += prime_list[R]
        R += 1

    if total == N:
        ans += 1
print(ans)

보석쇼핑

이번엔 수열의 합이 아니라 보석 종류의 합이다. 보석의 수는 중요하지 않고 '종류'만 중요하므로 key-value(종류-개수)인 자료구조를 이용한다. C++이라면 map을, python이라면 dictionary를 이용하여 map/dictionary의 개수를 비교한다.
또 그 길이도 짧은 것을 비교해야한다는것을 염두한다.

def solution(gems):
    answer = []
    
 
    D = dict()          
    for item in gems:
        D[item] = 1
    target = len(D)
    # target = len(set(gems))로 간결하게 작성이 가능하다.

    start, end = 0, 0
    N = len(gems)
    D = dict()
    D[gems[0]] = 1   # 일단 보석 한개를 넣는다.
    answer = [1, N]  # 가장 긴 길이를 저장

    while start < N and end < N:
        if len(D) == target:
            # 가장 짧은 길이를 저장한다.
            if answer[1] - answer[0] > end - start:
                answer = [start + 1, end + 1] # 인덱스 조정

            # 보석 삭제
            if D[gems[start]] == 1:
                del D[gems[start]]
            else:
                D[gems[start]] -= 1
            start += 1

        else:
            # 추가할 인덱스 증가. 범위 확인
            end += 1
            if end == N:
                break
            
            # 보석 추가
            if gems[end] in D:
                D[gems[end]] += 1
            else:
                D[gems[end]] = 1

    return answer