[BOJ/백준] 16472 고냥이

from collections import defaultdict
 
N = int(input())
 
arr = list(input())
 
cnt_dict = defaultdict(int)
result = 0
prev_idx = -1
for idx in range(N):
    alpha = arr[idx]
    cnt_dict[alpha] = idx
    if len(cnt_dict) > N:
        min_idx = 100001
        min_key = -1
        for key in cnt_dict:
            if min_idx > cnt_dict[key]:
                min_idx = cnt_dict[key]
                min_key = key
        prev_idx = min_idx
        del cnt_dict[min_key]
    
    result = max(result,idx-prev_idx)
print(result)

 

 

전형적인 두 포인터 문제이고, 그걸 다른 방식으로 푼 것이다. 

 

defalutdict를 통해, 각 알파벳의 마지막 위치를 저장시켜주고,

 

그 길이가 N을 넘어서게 되면, 마지막 위치가 가장 작은 알파벳을 삭제해주는 방식으로 해주고

 

prev_idx를 갱신해준다

 

위와 같은 방식을 통해 문제를 풀어주면 된다.

 

 

 

   .