기본문제로 오랜만에 투 포인터 알고리즘 재활하기1

1. 문제

 

14246번: K보다 큰 구간 (acmicpc.net)

14246번: K보다 큰 구간

 

2. 풀이

 

첫번째 핵심

두개의 포인터 i,j를 두고 i~j까지의 합이 k보다 작다면, 끝 포인터 j를 1칸 늘린다.

 

모든 수가 자연수이기 때문에 끝 포인터 j를 1칸 늘리면 구간 합이 증가하게 된다

 

------------------------------------------------------------------------------------------------------------

 

두번째 핵심

반대로 i~j까지의 합이 k보다 크다면, 그 순간 j부터 끝까지는 모두 k보다 크므로 n-1 - j + 1을 counting해주고

 

시작포인터 i를 1칸 늘려주고, 끝 포인터 j를 i로 옮겨주고 summation도 A[i]로 초기화

 

 

세번째 핵심

여기서 구간합은 어떻게 구할까? 매 순간 sum(A[i:j+1])을 해줘? 그게 아니라 A[i]부터 시작한 summation을 

 

j가 1칸 늘어날때마다, A[j]를 누적해서 더해주면 된다

 

from sys import stdin

n = int(stdin.readline())

A = list(map(int,stdin.readline().split()))

k = int(stdin.readline())

i = 0
j = 0

summation = A[0]

answer = 0

while j <= n-1 and i <= j:
    
    if summation > k:
        
        answer += (n-j)

        i += 1
        j = i
        summation = A[i]
    
    else:
        
        j += 1

        if j == n:
            
            break

        summation += A[j]
    
print(answer)

 

근데 사실 이건 브루트포스나 다름이 없다

 

포인터만 2개 썼지, 투 포인터를 제대로 활용하지 못해 시간복잡도를 줄이지 못한 경우이다.

 

핵심아이디어로 구간합이 적으면 끝포인터 1칸 늘려주는건 잘 기억하고 있지만...

 

 

3. 최적화된 풀이

 

시간복잡도를 줄일려면, 끝 포인터가 j에서 k보다 큰 순간을 찾고 가능한 구간 수를 더한 다음

 

시작 포인터 i를 1칸 늘리더라도 끝 포인터 j를 다시 시작 포인터 i로 안옮기는게 포인트다.

 

어떻게 가능할까

 

역시 시작 포인터 i,j를 0으로 두고 초기값은 A[0]

 

from sys import stdin

n = int(stdin.readline())

A = list(map(int,stdin.readline().split()))

k = int(stdin.readline())

i = 0
j = 0

summation = A[0]

answer = 0

 

그리고 현재 구간의 합과 k를 비교하기 시작

 

현재 구간 합 summation보다 k가 크다면... 현재 시점의 [i,j]에서 j이후로는 구간합이 모두 k보다 클 것이므로

 

구간의 개수 answer에 n-1-j+1 = n-j를 더해준다.

 

그리고 시작포인터 i를 1칸 옮겨주고 이전 i-1의 정수값을 현재 구간합에 빼줘서 구간합을 유지시킨다.

 

여기서 다시 j = i로 돌아가는게 결국 비효율적인 중복연산을 하게 되는 부분이다

 

조금만 생각해보면 어차피 다시 summation > k 비교하면서 이전의 j로 돌아가게 될거거든

 

while 1:
    
    if summation > k:
        
        answer += (n-j)

        i += 1
        summation -= A[i-1]

 

 

근데 현재 구간합이 k보다 작거나 같다면 어떨까?

 

그냥 끝 포인터 j를 1칸씩 옮겨주고 구간합을 구해준다.

 

구간합은 summation에 이동한 포인터 j에 대해 A[j]만 더해주면 끝이다

 

근데 이제 문제는... j가 이동하면서 n이 될수가 있어 

 

그럴때 A[j]로 접근하면 A의 끝 index는 n-1이다보니 에러가 나겠지

 

그래서 j가 n이 되어 끝포인터가 끝지점에 도달했다면.... 반복문을 탈출하면 된다.

 

왜 탈출해도 될까?

 

현재 지점은 summation이 k보다 작거나 같은 부분이기 때문에,

 

구간을 최대로 늘려도 여전히 summation이 k보다 작으므로, 아무리 해도 k보다 큰 경우는 찾을 수 없기 때문이다.  

 

from sys import stdin

n = int(stdin.readline())

A = list(map(int,stdin.readline().split()))

k = int(stdin.readline())

i = 0
j = 0

summation = A[0]

answer = 0

while 1:
    
    if summation > k:
        
        answer += (n-j)

        i += 1
        summation -= A[i-1]
    
    else:
        
        j += 1

        if j == n:
                 
            break
           
        summation += A[j]
    
print(answer)