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

백준 30804 - 과일 탕후루

시간 제한 2초, 메모리 제한 1024MB

# 조건

• 은하는 긴 막대에 $N$개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다.
• 과일의 각 종류에는 $1$부터 $9$까지의 번호가 붙어있고, 앞쪽부터 차례로 $S_1, S_2, \cdots, S_N$번 과일이 꽂혀있습니다.
• 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.
• 탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 $a$개, 뒤에서 $b$개의 과일을 빼면 $S_{a+1}, S_{a+2}, \cdots, S_{N-b-1}, S_{N-b}$번 과일, 총 $N-(a+b)$개가 꽂혀있는 탕후루가 됩니다. $(0 \le a, b;$ $a+b < N)$ 

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

입력

• 첫 줄에 과일의 개수 N이 주어집니다.(1<=N<=200,000)
• 둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N개의 정수 S1, ... , SN이 공백으로 구분되어 주어집니다.

출력

• 문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

# 접근 방법

• 투 포인터로 풀어주었다.
• left와 right를 사용하여 현재 과일의 개수를 기록해주고, 과일의 종류를 species set에 넣어주었다.
• 2개 이하라면 result를 max값으로 갱신, 2개보다 많다면 left의 과일 수를 -1해주고, 0개라면 species에서 제거 후 left += 1을 해주었다.
• 또한, 투 포인터가 아닌 for문으로 풀어주어도 상관이 없다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
nums = list(map(int, input().split()))
result = 0

have = defaultdict(int)
left = 0
right = 0
have[nums[left]] += 1
species = set()
species.add(nums[0])
while right < N:

    if len(species) <= 2:
        result = max(result, right-left+1)
        right += 1
        if right < N:
            have[nums[right]] += 1
            species.add(nums[right])
    else:
        have[nums[left]] -= 1
        if have[nums[left]] == 0:
            species.remove(nums[left])
        left += 1

print(result)

import sys
input = sys.stdin.readline
from collections import defaultdict
N = int(input())
nums = list(map(int, input().split()))
result = 0

fruits = [0] * 10
have = defaultdict(int)
spe = 0
total = 0
st = 0

for i in range(N):
    if have[nums[i]] == 0:
        spe += 1
    have[nums[i]] += 1
    total += 1

    if spe <= 2:
        result = max(result, total)
    else:
        have[nums[st]] -= 1
        if have[nums[st]] == 0:
            spe -= 1
        st += 1
        total -= 1

print(result)