수들의 합 2 ( 2003 번 )

2003번: 수들의 합 2

 

---

🧠 알고리즘

• 투 포인터 (Two Pointer) / 슬라이딩 윈도우 (Sliding Window)

 

✔️ 동작 방식

• 왼쪽(l)과 오른쪽(r) 포인터를 사용해 구간의 합(now_num)을 관리.
• 현재 합이 m 이상일 경우 → 왼쪽 포인터(l)를 한 칸 이동하며 구간을 줄임.
  • 이때 now_num == m이면 경우의 수(answer) 1 증가.
• 현재 합이 m 미만일 경우 → 오른쪽 포인터(r)를 한 칸 이동하며 구간 확장.
• 오른쪽 포인터가 끝(n)에 도달하면 종료.
• 결과적으로, 연속된 부분 구간의 합이 m이 되는 경우의 수를 구함.

---

 

🧾 코드

import sys

def _main():
    answer = 0
    l, r, number = -1, -1, 0

    while l <= r:
        if number < m:
            r += 1
            if r == n: # 종료 조건
                break
            number += n_list[r]
        else:
            if number == m:
                answer += 1
            l += 1
            number -= n_list[l]

    return answer


n, m = map(int, sys.stdin.readline().rstrip().split())
n_list = tuple(map(int, sys.stdin.readline().rstrip().split()))

print(_main())

---

 

⏱️ 시간 복잡도

while l <= r : 각 원소를 한번 씩 탐색 ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )