[Python] 백준 30804번 과일 탕후루 | 투포인터, 브루트포스 알고리즘

제목은 달콤하지만 ...^^ 호락호락하지 않았던 문제,,

 

투 포인터 유형은 보통 arr[start, end+1]의 합으로 풀어야 하는 문제가 많았는데,

이 문제는 종류의 개수를 확인하며 풀어야 한다!!

 

첫번째 시도

[ 슬라이딩 윈도우 + 매개변수 찾기 + 투포인터 ] 로 풀이했으나 시간 초과 !!!!!! 🥹🥹

from copy import deepcopy

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

num = {}

for s in S:
    if s in num:
        num[s] += 1
    else:
        num[s] = 1

kind = len(set(S))

if kind == N:
    print(2)

elif kind <= 2:
    print(N)

else:
    def tanghuru(max_num, kind):
        start, end = 0, max_num - 1
        num_i = deepcopy(num)
        while end < N:
            if kind <= 2:
                return True
            if end == N-1:
                return False
            num_i[S[start]] -= 1
            if num_i[S[start]] == 0:
                kind -= 1
            start += 1
            end += 1
            num_i[S[end]] += 1
            if num_i[S[end]] == 1:
                kind += 1
    
    max_num = N
    while max_num > 0:
        if tanghuru(max_num, kind) == True:
            break
        else:
            max_num -= 1
            num[S[max_num]] -= 1
            if num[S[max_num]] == 0:
                kind -= 1
    
    print(max_num)

 

max_num로 최대 길이를 고정하고 그 안에서 슬라이딩 윈도우로 움직이면서

• 가능하면 break, max_num 출력
• 불가능하면 max_num -= 1, kind 조정

이런 식으로 풀었었는데, 이중 while 문이 쓰이게 되면서 시간 복잡도가 O(n^2)이 되어 버려 시간 초과가 나는 듯 했다,,

 

성공 !!

[ 투포인터 + 재귀 ]  알고리즘을 활용하여 다시 풀었당.

import sys
sys.setrecursionlimit(10**6)

N = int(input())
S = list(map(int, input().split()))
num = [0] * 10

def tanghuru(start, end, max_num, kind):
    global N
    if end >= N:
        return max_num
    
    num[S[end]] += 1
    if num[S[end]] == 1:
        kind += 1
        
    if kind > 2:
        num[S[start]] -= 1
        if num[S[start]] == 0:
            kind -= 1
        start += 1
    
    max_num = max(max_num, end - start + 1)
    return tanghuru(start, end+1, max_num, kind)
    
print(tanghuru(0, 0, 0, 0))

 

단, 이때 재귀함수의 recursion error가 뜨므로

처음에 sys.setrecursionlimit 설정을 해주어야 함

 

end를 고정해두고 종류의 개수가

2개 이하이면 end를 N보다 작을 때에 한해 하나씩 뒤로 움직이고,

2개가 넘어가면 start를 하나씩 뒤로 움직인다.

그 과정에서 최대 길이를 max_num으로 저장하여 return 하는 과정이다.

 

이렇게 하면 시간 초과 없이 맞았습니다!! 를 볼 수 있다 !