[백준][투포인터] 16472.고냥이

16472.고냥이

 

• 내 풀이
  • 최장연속부분수열 문제랑 유사하다고 생각해서 투포인터로 접근
  • 처음에는 리스트에 append, pop 하면서 진행했더니 79%에서 시간초과남
    • pop(0)은 O(n)이라서 문자열이 길면 시간초과  
    • ⇒ defaultdict 으로 갯수만 체크하니까 시간 효율 향상됨
  • 딕셔너리 key 삭제할땐 del dict[key]

from collections import defaultdict
n=int(input())
cat=list(input().rstrip())

tmp=defaultdict(int)
l,r=0,1
tmp[cat[l]] += 1
tmp[cat[r]] += 1
answer=0
while l<r and r<len(cat):

    if len(tmp)<=n:
        answer = max(answer, sum(tmp.values()))
        r+=1
        if r>=len(cat):
            break
        tmp[cat[r]] += 1
    else:
        tmp[cat[l]] -= 1
        if tmp[cat[l]]==0:
            del tmp[cat[l]]
        l+=1
print(answer)

 

• 다른 사람 풀이

from collections import defaultdict

n = int(input())
cat = input().rstrip()

count = defaultdict(int)
l = 0
answer = 0

for r in range(len(cat)):
    count[cat[r]] += 1

    while len(count) > n:
        count[cat[l]] -= 1
        if count[cat[l]] == 0:
            del count[cat[l]]
        l += 1

    answer = max(answer, r - l + 1)

print(answer)