77. Longest Repeating Character Replacement

🎯 leetcode - 424. Longest Repeating Character Replacement

---

🎯 투 포인터 + 슬라이딩 윈도우로 풀기

📌 문제

- 파이썬 알고리즘 인터뷰 77번 문제

📌 날짜

2020.03.07

📌 시도 횟수

5 try

💡 Code

from collections import Counter
from collections import defaultdict


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left, right = 0, 0
        max_len = 0
        visited = Counter() # 현재 가지고 있는 문자 종류와 개수를 저장 
        while left <= right and right < len(s):
            visited[s[right]] += 1

            max_freq = visited.most_common(1)[0][1] 
            
            # 만약 전체 문자의 수에서(right-left+1) 가장 많이 등장한 수(max_freq)를 뺀 값이 k보다 크다면 
            # '바꿀 수 있는 최대 횟수'를 초과한 것이므로 먼저 방문한 문자들을 차례부터 차례대로 뺀다.
            if (right - left + 1) - max_freq > k:
                visited[s[left]] -= 1
                left += 1
            else:
                max_len = max(max_len, right - left + 1) # 만들 수 있는 가장 긴 길이를 갱신함
            
            right += 1
            
        return max_len

💡 문제 해결 방법

📍 슬라이딩 윈도우로 오른쪽 포인터(right)를 계속 우측으로 이동한다.
📍 단, 만약 변경가능한 최대 횟수(k)를 넘으면, 왼쪽 포인터(left)를 우측으로 이동시켜서 범위를 조절한다.
- `max_freq = visited.most_common(1)[0][1]`는 현재 범위에서 가장 많이 등장한 문자의 개수이다.
- (right - left + 1)은 현재 범위 안에 있는 모든 문자들의 개수이다.
- `(right - left + 1) - max_freq`는 가장 많이 등장한 문자를 제외한 문자들의 개수로,
   변경 가능한 문자들의 개수를 의미하기도 한다!
- 따라서 if (right - left + 1) - max_freq > k: 는 변경 가능한 횟수를 초과했을 때를 검사한다.
📍 max_len을 갱신해줌으로써 만들 수 있는 가장 긴 길이를 max_len에 저장한다.

💡 새롭게 알게 된 점

- Counter은 dict와 비슷한 것 같다!
- Counter 클래스를 사용하면 most_common이라는 메소드를 사용할 수 있다.

📍 most_common

collections.Counter(a).most_common(n) : a의 요소를 세어, 최빈값 n개를 리스트에 담긴 튜플형태로 반환한다.

Counter("AAABAAB")
>> Counter({'A': 5, 'B': 2})

Counter("AAABBFFD").most_common(2)
>> [('A', 3), ('B', 2)]	# 최빈값 2개를 반환한다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 문제를 잘못 이해했었다😢 문제를 좀 똑바로 읽어야 겠다..

---