[백준] 30804 | 과일 탕후루 [파이썬/python]

문제

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

문제에서는 탕후루에 꽃힌 과일의 종류를 숫자(1~9)로 구분하여 제공한다. 막대의 앞쪽, 뒤쪽에서 과일을 제거해 탕후루에 꽂힌 과일을 두 종류 이하로 만들었을 때 가질 수 있는 과일 개수의 최대값을 구하는 문제이다.

 

접근

같은 종류인 과일은 연속되어도 상관없으므로 입력받은 탕후루 내 과일 목록을 [종류, 개수] 형태로 정리해 리스트에 저장했다. 같은 종류 과일이 연달아 나올 경우 이렇게 바꾸어 계산하면 더 효율적일 것이라고 판단했다.

ex) 5, 1, 1, 2, 1 -> [5, 1], [1, 2], [2, 1], [1, 1]

이후, 집합을 활용해 현재 확인 중인 범위 내 과일을 두 종류 이하로 제한하며 과일 개수를 세고, 최대값을 구해 출력한다.

 

코드

N = int(input())
tangs = list(map(int, input().split()))
fruits = [[0, 0]]

for t in tangs:
    if fruits[-1][0] == t:
        fruits[-1][1] += 1
    else:
        fruits.append([t, 1])
       
s = set()
ans = 0
cnt = 0
for i in range(1, len(fruits)):
    if fruits[i][0] not in s and len(s) == 2:
        ans = max(ans, cnt)
        s = {fruits[i-1][0], fruits[i][0]}
        cnt = fruits[i-1][1] + fruits[i][1]
    else:
        s.add(fruits[i][0])
        cnt += fruits[i][1]
        
print(max(ans, cnt))