투포인터 안녕? (#30804 과일 탕후루)

#30804 과일탕후루 https://www.acmicpc.net/problem/30804

 

투포인터가 처음이라서 자료를 참고하면서 했다.

 

이름만 들었을 때 간단한 개념일 것 같아서 별도로 학습하지 않았지만

생각보다 고려해야할 점이 많았다.

 

 

중요한 점은, right는 순차적으로 증가하되 left는 특정 조건을 만족할 때 갱신해야한다는 점이다.

물론, 모든 문제에서 이럴 것 같지는 않다.

 

 

투포인터의 장점은, O(n)의 시간복잡도로 해결할 수 있다는 점이다.

되게 좋은 솔루션을 배운 기분이다.

 

 

import sys

input = sys.stdin.readline

n = int(input())

fruits = [int(x) for x in input().split()]


# 투 포인터 알고리즘
# left,right 포인터를 갖는데, right는 지속 증가하되, left가 특정 조건에서 증가하도록 해야함.
# left 포인터는 1씩 증가하는게 아니다. 특정 조건을 만족하는 위치로 이동하는 것.
# 이 문제에서 조건은, 다른 숫자가 나왔을 때인 것 같다.
left, right = 0, 1
kind = set()
kind.add(fruits[left])

next_left = 0

answer = 0
while right < n:
    # 기존에 과일의 종류가 하나라면, 두 개가 될 때까지 계속 더할 수 있다.
    if len(kind) == 1:
        if fruits[right] not in kind:
            kind.add(fruits[right])

    else:  # 과일의 종류가 두 개라면
        # right 포인터의 과일이 선택한 과일이 아닌 경우 -> 조건 초과.
        if fruits[right] not in kind:
            # 정답 한 번 계산하기
            # print(fruits[left:right])
            answer = max(answer, right - left)

            # 더 이상 right 포인터를 증가시킬 수 없으니 left 갱신하기

            # 먼저 kind에 있는 값 갱신
            kind = set()
            kind.add(fruits[next_left])
            kind.add(fruits[right])
            left = next_left
    # left 포인터가 이동할 위치 기억하기
    # 과일이 달라지는 지점이 새로 이동할 위치
    if fruits[right - 1] != fruits[right]:
        next_left = right
    right += 1

# 위 루프에서는 맨 마지막 아이템을 계산하지 않는다.
# 따라서, left 부터 맨 마지막 값 까지의 길이를 반영해줄 필요가 있다.
print(max(answer, n - left))