[백준 30804번 알고리즘] 과일탕후루 파이썬 풀이 및 반례

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

 

 

실버 2 과일 탕후루 문제입니다.

우선 간단하게 완전탐색식 사고를 가지고 문제를 풀어보겠습니다.

 

import sys
input = sys.stdin.readline
def check(i,j):
    return len(set(tang[i:j+1]))

n = int(input().strip())
tang = [int(x) for x in input().strip().split()]
if n == 1:
    print(1)
    sys.exit()
a = 0
b = n-1

while 1:
    if check(a,b) <= 2:
        print(b-a+1)
        break
    
    if check(a+1,b) <= check(a,b-1):
        a += 1
    else:
        b -= 1

 

 

이렇게 풀면 반례는 다 통과하지만

제출을 눌러보면 시간초과라고 출력될겁니다.

이유는 배열에 있는걸 하나하나 다 확인해야하고 set을 사용해서 시간이 오래걸린겁니다.

하지만 우리는 이 생각을 바탕으로 문제를 풀어나갈건데

투포인터라는 방법을 사용을 할겁니다.

 

포인터 두개 다 왼쪽에 두면서 "right" 포인터를 오른쪽으로 계속 이동시켜줍니다.

이때 우리는 max_length라는 변수에 최대값을 계속 저장해줄겁니다.

종류가 2개가 초과됐다?

왼쪽 포인터를 종류가 2개가 될때까지 오른쪽으로 이동시켜줍니다.

이 과정을 코드로 표현했습니다.

 

 

 

def max_fruit_tanghulu_length(N, fruits):
    from collections import defaultdict
    
    # 투 포인터 초기화
    left = 0
    right = 0
    fruit_count = defaultdict(int)
    max_length = 0
    
    while right < N:
        # 오른쪽 포인터가 가리키는 과일 추가
        fruit_count[fruits[right]] += 1
        
        # 과일 종류가 2개를 초과하면 왼쪽 포인터 이동
        while len(fruit_count) > 2:
            fruit_count[fruits[left]] -= 1
            if fruit_count[fruits[left]] == 0:
                del fruit_count[fruits[left]]
            left += 1
        
        # 현재 상태에서 최대 길이 갱신
        max_length = max(max_length, right - left + 1)
        right += 1
    
    return max_length

# 입력 받기
N = int(input().strip())
fruits = list(map(int, input().strip().split()))

# 결과 출력
print(max_fruit_tanghulu_length(N, fruits))

 

반례 제공드리겠습니다.

10
7 5 5 2 4 2 2 5 5 5

ans: 5
=====

16
1 2 2 2 1 2 3 2 2 2 2 2 2 1 1 2

ans: 9  
=====
5
1 2 3 3 3

ans: 4  
=====
5
1 2 3 2 1

ans: 3  
=====
10
1 1 1 1 1 1 1 1 2 3

ans: 9

 

 

도움이 되셨다면 공감버튼 한번 눌러주세요. 로그인 안해도됩니다!