[파이썬] 백준 30804 : 과일탕후루 (실버2)

[파이썬] 백준 30804 : 과일탕후루 (실버2)

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

---

풀이

방향성 생각

• 각 시작지점마다 가능한 길이를 찾는다.
• $NlogN$이하로 해야하므로, 투포인터로 찾는다.
• 각 과일 개수를 카운팅해줘야 하므로 딕셔너리 하나 사용해주기

---

전체코드

from collections import defaultdict as dd

N = int(input())
arr = list(map(int,input().split()))

l,r,count = 0,0,0
infos = dd(int)
answer = 0
while r<N:
    if infos[arr[r]] == 0:
        count += 1
    infos[arr[r]] += 1

    while count > 2:
        infos[arr[l]] -= 1
        if infos[arr[l]] == 0:
            count -= 1
        l += 1

    answer = max(answer,r-l+1)
    r += 1

print(answer)

코멘트

• 보통 이정도는 골5같은데 대회나가는 사람들이 풀어서 좀 내려간듯?