과일 탕후루

30804번: 과일 탕후루

 

나의 풀이

import sys
input = sys.stdin.readline

cd_ct = int(input())
cd_list = list(map(int, input().rstrip().split()))

cd_dict =  {}
max_len = 0
    
left_pt = 0
for i in range(cd_ct):  
    now_cd = cd_list[i]
    if now_cd not in cd_dict:
        cd_dict[now_cd] = 1
    else:
        cd_dict[now_cd] += 1
    
    while len(cd_dict) > 2:
        del_cd = cd_list[left_pt]
        cd_dict[del_cd] -= 1
        if cd_dict[del_cd] == 0:
            cd_dict.pop(del_cd)
        left_pt+=1
        
    max_len = max(max_len, i-left_pt+1)
print(max_len)

 

시간 복잡도

for i in range(cd_ct) : 리스트를 순회 하며 최대 길이를 구함 ( 선형 시간 복잡도 )
    내부 루프 : (상수 시간 )
해당 알고리즘 시간 복잡도는 : 선형 시간 복잡도 ( O(n) )