Intro

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

Two Pointer

정의

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

문제

• 21921번: 블로그

• 

풀이

풀이 과정

시간초과 코드

• 완전 탐색으로 구현을 한다면, 매 시작점마다 X일 후까지의 합을 구하는 코드를 생각할 수 있다.

# boj 21921.블로그

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

m = 0   # 현 시점에서의 최대 방문자수
ans = 0 # 최대 방문자 수에 해당되는 기간의 개수

for left in range(n - x + 1):
    right = left + x
    cnt = sum(nums[left:right])

    if cnt == m:
        ans += 1
    elif cnt > m:
        ans = 1
        m = cnt

if m == 0:
    print('SAD')
else:
    print(m, ans, sep='\n')

• (N-X)개의 시작점에서 X만큼 반복하여 합을 구해야 함 -> 시간복잡도: O(X^2)
• X의 범위가 250,000까지 이므로 1억에 1초일 경우 1초를 아득히 넘어선다.

코드 설명

아이디어

• 매 시작점에 대해 합을 구할 때, '이전 시작점의 값'과 '새로운 끝점의 값'을 제외한 나머지는 합에 포함됨
• 따라서, 합을 유지하면서 맨 앞과 맨 뒤 값만 더하고 빼는 과정만 추가
• 이를 통해, 시간복잡도를 O(X^2)에서 O(N)으로 줄일 수 있음

제출 코드

# boj 21921.블로그

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

# 등간격으로 움직이는 포인터 두개(1개로 관리 가능)
left = 0
right = x

# 초기값 설정
m = sum(nums[left:right])
ans = 1
cnt = m

# 시간복잡도: O(n)
while right < n:
    cnt = cnt - nums[left] + nums[right]

    if cnt == m:
        ans += 1
    elif cnt > m:
        ans = 1
        m = cnt
    right += 1
    left += 1

if m == 0:
    print('SAD')
else:
    print(m, ans, sep='\n')

• 이해를 돕기 위해 left, right를 각각 사용했지만, 간격이 항상 일정하므로 하나만 있어도 됌

제출 결과

Outro

• 또 늦잠 자느라 아침에 못 풀었음