Intro

• 이번 주 알고리즘 스터디에서 풀 문제 유형은 'Two Pointer'이다.

Two Pointer

정의

• 구간의 양 끝을 가리키는 2개의 포인터를 사용하는 풀이기법
• 2개의 포인터가 한 방향으로만 계속 전진하는 형태에서 주로 쓰임

문제

• 2003번: 수들의 합 2

• 

풀이

풀이 과정

• i번째 부터 j번째 까지 순서대로 합을 구해야 하는 문제
• 즉, 합을 구하는 방향이 한 방향으로만 이루어진다고 볼 수 있음

코드 설명

• left와 right를 0부터 시작

• right pointer를 이동시키면서 배열의 숫자를 더해나감
• target(m)보다 크거나 같아지면 right의 이동을 멈춤

• 현재까지의 합이 target과 같으면 ans의 값 1 증가
• 현재까지의 합(cnt)에서 left pointer가 가리키고 있는 값을 빼줌과 동시에 left pointer 이동

제출 코드

# boj 2003. 수들의 합2

# 입력 받기
n, m = tuple(map(int, input().split()))
nums = list(map(int, input().split()))

# sum(nums[i]~nums[j]) = m인 경우의 수
# 투포인터 사용
right = 0
cnt = 0
ans = 0
# left pointer를 하나씩 확인하면서
for left in range(n):
    # right pointer를 이동시키면서
    # n보다는 작고, 합이 m보다는 작은 동안
    # 합을 구해주기
    # cnt >= m 이면 종료
    while right < n and cnt < m:
        cnt += nums[right]
        right += 1
    
    # 합이 m이라면 경우의 수 증가
    if cnt == m:
        ans += 1
    
    # left pointer를 이동시킬 것이므로
    # left 위치의 값을 빼주기
    cnt -= nums[left]

print(ans)

제출 결과

Outro

• 매일 아침 알고리즘 스터디를 모여서 진행하는데 늦잠 자느라 늦게 참석함,,,
• 오전 08:14분부터 풀기 시작하여 약 30분 정도 소요됨
• 이제 시작 인증샷과 종료 인증샷도 함께 올릴 예정