백준 파이썬 30804번 과일 탕후루 (Today I Learn 2025.04.02)
백준 파이썬 공부 2025.04.02
30804번 과일 탕후루 (실버 2)
1. 문제
은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다.
과일의 각 종류에는 1부터 9까지의 번호가 붙어있고,
앞쪽부터 차례로 S_1, S_2, ..., S_N번 과일이 꽂혀있습니다.
과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니
과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.
탕후루를 다시 만들 시간이 없었던 은하는,
막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다.
앞에서 a개, 뒤에서 b개의 과일을 빼면 S_{a+1}, S_{a+2}, ..., S_{N-b-1}, S_{N-b}번 과일,
총 N-(a+b)개가 꽂혀있는 탕후루가 됩니다. (0 <= a, b, a+b < N)
이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서,
과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.
2. 입력
첫 줄에 과일의 개수 N이 주어집니다. (1 <= N <= 200,000)
둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N개의 정수 S_1, ..., S_N이 공백으로 구분되어 주어집니다. (1 <= S_i <= 9)
3. 출력
문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서,
과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.
4. 문제 풀이
투 포인터로 포인터 두개를 이동해가면서
두 포인터 사이의 과일 갯수를 확인하면서 최대의 길이를 검사하면 된다.
>>>코드
import sys
n = int(sys.stdin.readline().strip())
Tanghulu = list(map(int, sys.stdin.readline().strip().split()))
p1, p2 = 0, 0
length = 0
cnt = {}
while p2 < n:
# p2 위치의 과일 갯수와 종류 갱신
if Tanghulu[p2] in cnt:
cnt[Tanghulu[p2]] += 1
else:
cnt[Tanghulu[p2]] = 1
# cnt 의 길이 (과일의 종류)가 2개가 넘어가면 과일의 종류가 2개가 될 때까지
while len(cnt) > 2:
# p1 위치의 과일을 제거하면서
cnt[Tanghulu[p1]] -= 1
if cnt[Tanghulu[p1]] == 0:
del cnt[Tanghulu[p1]]
# p1을 이동
p1 += 1
# 최대 길이 갱신
length = max(length, p2 - p1 + 1)
p2 += 1
print(length)