실력진단

이번엔 dp 문제도 제대로 풀고 hashmap 문제도 풀었다.
그 다음 나온 문제는 완전탐색 문제 같았는데, 이 문제가 이렇게 뒤에 나올리 없으니 틀리겠거니 하고 시간초과나서 못풀었다.

투포인터

이 문제 유형은 투포인터 문제였다.

완전탐색으로 풀 수 있지만, 그러면 시간복잡도가 O(n^3) 까지 나오는데, 투포인터로 풀면 O(n) 으로 풀 수 있다.

문제 : https://www.codetree.ai/missions/8/problems/shortest-subtotal?&utm_source=clipboard&utm_medium=text

문제가 아직 익숙치 않아 떠듬떠듬 풀어보고 있다.

i 와 j 포인터로 조건문을 지켜가며 밀당(?) 잘 해야 하는 문제다.

import sys
n, s = map(int, input().split())

nums = list(map(int, input().split()))

ans = sys.maxsize

sum_val = 0
j = 0
for i in range(0, n):
    #print(i, j , sum_val)
    while j <= n - 1 and sum_val < s:

        sum_val += nums[j]
        j += 1
        #print('while', i, j , sum_val)

    if sum_val < s:
        break
    
    ans = min(ans , j - i)

    sum_val -= nums[i]

if ans == sys.maxsize:
    ans = -1

print(ans)

말로 설명하긴 어렵고 코드트리에서 동영상으로 어떻게 알고리즘이 동작하는지 보여주는데, 훨씬 이해하기 쉬웠다.

요점은 i 와 j 의 위치를 바탕으로 처음엔 j 를 늘려가고 while 조건문에 안맞으면, 그 다음은 i 를 밀어 계산하고... 이를 반복한다.

무엇보다 복잡도가 확 내려가기 때문에 이모저모 응용하기 좋은 알고리즘이다.
이번주에는 투포인터만 쭉 풀어봐야겠다....!