[백준] 2003번 수들의 합 2 - Python

이번에 해결해 볼 문제는 백준에 있는 2003번 수들의 합 2입니다.

이번 포스트에서 해당 문제를 해결하고자 하는 이유는 Two-Point와 Sliding Window 알고리즘에 대해 공부해 볼 필요가 있기 때문입니다. 몇 번의 코딩테스트를 치루면서 가장 크게 느꼈던 점은 공부하지 않은 알고리즘이 나온 경우 다른 알고리즘으로 해결하기 쉽지 않다는 점입니다. 이러한 이유 때문에 시간은 시간대로 낭비하고 문제는 해결하지 못한 경우가 많았습니다. 그 중 Two-Point 알고리즘과 Sliding Window 알고리즘으로 해결해야 하는 문제가 나왔을 때 자료구조(큐, 덱)로 해결하거나 DFS, BFS로 해결하고자 했지만 해결하지 못했습니다. 그렇기 때문에 이번 포스트에서는 Two-Point와 Sliding Window에 관련된 문제를 해결하고자 합니다.

두 알고리즘에는 구간의 길이가 고정되어 있는지 유동적인지의 차이만 있을 뿐 크게 다르지 않습니다. 구간의 길이가 고정되어 있으면 Sliding Window, 유동적이면 Two-Point입니다. 다른 알고리즘으로 해결하지 못하는 가장 큰 이유는 시간 복잡도가 아닐까 싶습니다. 코딩 테스트에서 가장 복잡하게 나온다면 시간복잡도가 $O(N{log}N)$이지만 위의 두 알고리즘은 $O(N)$으로 해결 가능합니다. 그렇기 때문에 두 알고리즘을 떠오릴 수만 있다면 자주 등장하는 알고리즘은 아니지만 쉽게 해결하고 넘어갈 수 있지 않을까 싶습니다.

---

문제 설명

• 하나의 리스트 arr이 주어졌을 때 인덱스 i부터 j까지의 합이 M이 되는 경우의 수를 구하는 문제입니다.

문제 해결 아이디어

• 리스트에서 연속된 원소들의 합이 M이 되는 경우의 수를 구하는 것이기 때문에 Two-Point 알고리즘을 사용해 문제를 해결할 수 있습니다.
• 해당 문제에서는 자연수라는 조건이 주어졌으므로 아래와 같이 경우를 나눠볼 수 있습니다.
  • 구간의 합(val)이 M인 경우
    • 이미 구간의 합(val)이 M이므로 i와 j 모두를 1씩 더해주며 구간을 이동 시켜줍니다.
  • 구간의 합(val)이 M보다 큰 경우
    • 구간의 합(val)이 M보다 크므로 시작점 i를 하나 이동시켜 줍니다.
  • 구간의 합(val)이 M보다 작은 경우
    • 구간의 합(val)이 M보다 작으므로 끝점 j를 하나 이동시켜 줍니다.
• 이를 코드로 나타내면 아래와 같습니다.

문제 해결 코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
arr = list(map(int, input().split()))

answer = 0

i, j = 0, 1

while i < N and j <= N:
    val = sum(arr[i:j])

    if val == M:
        answer += 1
        i += 1
        j += 1
    elif val > M:
        i += 1
    else:
        j += 1

print(answer)