[백준/파이썬] 30804번: 과일 탕후루

문제

https://www.acmicpc.net/problem/30804

풀이

• N개의 과일
• 앞에서 a개, 뒤에서 b개 빼서 두 종류 이하의 과일로 이루어진 탕후루 만들기
• 두 종류 이하로 사용한 탕후루 중에서 과일 개수가 가장 많은 탕후루의 과일 개수

처음 문제를 접했을 때 set을 이용해서 개수를 판별하고 앞뒤 번갈아가면서 과일을 제거하는 방식으로 문제를 풀었었습니다.
그러나 시간초과가 발생했고 다른 방식이 필요하다는 생각이 들어 찾아봤습니다.

알고리즘 분류를 확인해보니 투 포인터로 분류가 되어있더군요.

투 포인터란❓

두 개의 포인터를 활용하여 배열이나 리스트를 효율적으로 탐색하는 기법
보통 정렬된 배열이나 연속된 구간을 다룰 때 많이 사용 된다.
이 알고리즘을 사용하면 O(N²) → O(N)으로 최적화할 수 있다.

투 포인터의 핵심

• 정렬된 배열 또는 리스트에서 탐색하는 경우
  정렬되어 있으면 두 포인터의 이동만으로 원하는 값을 빠르게 찾을 수 있다.
• 연속된 구간(슬라이딩 윈도우)에서 탐색하는 경우
  right를 증가시키며 범위를 확장
  만약 조건을 만족하지 않으면 left를 증가시켜 범위를 줄임

이 개념을 가지고 코드를 작성해보겠습니다.

cnt = {}
left,res = 0,0

과일의 종류와 개수를 저장할 딕셔너리를 선언하고 left와 결과를 저장할 변수를 선언합니다.

for right in range(n):
    cnt[arr[right]] = cnt.get(arr[right], 0) + 1

rigth를 이동하며 과일을 cnt에 저장
새 과일을 추가하며 right값 증가

만약 과일 종류가 3가지 이상이라면 left값 조정

    while len(cnt) > 2:
        cnt[arr[left]] -= 1
        if cnt[arr[left]] == 0: # 개수가 0이 되면 제거
            del cnt[arr[left]]
        left += 1

    res = max(res, right - left + 1) # 과일 개수 업데이트

최종적으로 결과 출력하면 끝 😋

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
cnt = {}
left,res = 0,0

for right in range(n):
    cnt[arr[right]] = cnt.get(arr[right], 0) + 1

    while len(cnt) > 2:
        cnt[arr[left]] -= 1
        if cnt[arr[left]] == 0:
            del cnt[arr[left]]
        left += 1

    res = max(res, right - left + 1)

print(res)