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

문제

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

 

풀이

첫 번째 시도

• 조건 : 두 종류 이하의 과일만 사용

탕후루의 최대 길이(N)부터 줄여가면서 모든 가능한 경우에 대해 문제의 조건을 만족하는지를 살폈다.

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

start, end = 0, N
answer = 0

# 탕후루 길이별로 체크
for i in range(N, 0, -1) :
  for j in range(0, N-i+1) :
    check = S[j:(j+i)]
    if len(set(check)) <= 2 :
      answer = max(answer, i)
      break
print(answer)

→ 시간 초과

 

두 번째 시도 (성공)

• 조건 : 두 종류 이하의 과일만 사용

투 포인터를 사용해 조건에 맞는 가장 긴 부분 리스트를 찾는 문제로 접근했다.

첫 번째 과일만 꽂는 것으로 시작해서 조건 만족 여부에 따라 포인터를 이동시키며 문제를 푼다.

포인터가 이동할 때 마다 탕후루에 꽂힌 과일의 종류를 세어준다.

 

1. 탕후루에 사용된 과일의 종류가 2개 이하인 경우

  조건에 맞는 경우이므로 탕후루의 길이를 계산하고, 오른쪽의 포인터를 이동한다.

 

2. 탕후루에 사용된 과일의 종류가 3개 이상인 경우

  조건에 맞지 않는 경우이므로 왼쪽의 포인터를 이동한다.

import sys
input = sys.stdin.readline

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

left, right = 0, 0
count = [0] * 10  # count[i] : i번 과일의 개수
count[S[0]] += 1
temp = [0] * 10  # temp[i] : i번 과일 존재 여부
temp[S[0]] = 1
kind = sum(temp)  # 과일 종류

answer = 1  # 정답 저장

while True :

  if kind <= 2 :  # 과일이 2종류 이하일때만 개수 세기
    answer = max(answer, sum(count))  # 정답 갱신
    right += 1
    if right == N :
      break

    count[S[right]] += 1
    temp[S[right]] = 1
    kind = sum(temp)

  else :  # 과일이 3종류 이상인 경우, 과일 종류가 하나 줄어들 때까지 왼쪽 과일 하나씩 빼기
    count[S[left]] -= 1
    if count[S[left]] == 0 :
      temp[S[left]] = 0
    kind = sum(temp)
    left += 1
    
print(answer)