77. Longest Repeating Character Replacement

리트코드

• 대문자로 구성된 문자열 s가 주어졌을 때 k번만큼의 변경으로 만들 수 있는, 연속으로 반복된 문자열의 가장 긴 길이를 출력하라.

1. 투 포인터, 슬라이딩 윈도우, Counter를 모두 이용

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        left = right = 0
        counts = collections.Counter()
        for right in range(1, len(s) + 1):
            counts[s[right - 1]] += 1
            
            #가장 흔하게 등장하는 문자 탐색
            max_char_n = counts.most_common(1)[0][1]
            
            #k 초과시 왼쪽 포인터 이동
            if right - left - max_char_n > k:
                counts[s[left]] -= 1
                left += 1
        #max_len = max(right-left, max_len) 비교 생략
        #max_len의 값은 바뀌지 않기 때문 (왼쪽, 오른쪽 함께 이동)
        return right - left
            
        

• 이 문제는 오른쪽 포인터가 계속 우측으로 이동한다는 점에서 슬라이딩 윈도우 문제이지만, 왼쪽 포인터를 계속 좁혀서 범위를 조절해 나간다는 점에서 76번 문제와 마찬가지로 투 포인터와 결합된 문제로 볼 수 있다.

• 최종 결과는 오른쪽 포인터에서 왼쪽 포인터 위치를 뺀 다음, 윈도우 내 출현 빈도가 가장 높은 문자의 수를 뺀 값이 k와 같을 수 있는 수 중 가장 큰 최댓값이라 정의할 수 있다.

	max(right) - min(left) - max_char_n == k

• 최대 길이를 찾는 문제이므로, right는 클수록 좋고, left는 작을수록 좋다.

  • AAABB라는 문자열이 있을 때 A를 B로 바꾸는 것은 3번,
    B를 A로 바꾸는 것은 2번의 연산이 필요하다.

  • 따라서 B를 A로 바꾸는 것이 연산 횟수 k를 최소화할 수 있는 방법이며, 이 계산은 마찬가지로 오른쪽 포인터 5에서 왼쪽 포인터 0을 뺀 다음, 출현 빈도가 가장 높은 문자인 A의 개수 3을 뺀 값, 5-0-3이 연산 횟수 k가 되며 이 값은 2가 된다.

• 왼쪽 포인터와 오른쪽 포인터를 0으로 지정한 다음, 오른쪽 포인터 right는 계속 우측으로 한 칸식 이동한다.

  • 이 때 Counter()를 이용해 가장 흔하게 등장하는 문자의 값을 계산해 나간다.

  • 가장 흔하게 등장하는 문자의 개수를 찾을 때 숫자로만 나열하다 보니, 가독성이 떨어지는 좋지 않는 코드가 되었는데, 다음 코드를 순서대로 살펴보면 어떤 식으로 원하는 결과를 가져오게 되는지 이해가 쉬울 것 같다.

      >>> counts

      Counter({'A': 3, 'B': 2})

      >>> counts.most_common()

      [('A', 3), ('B',2)]

      >>> counts.most_commont(1)

      [('A', 3)]

      >>> counts.most_commont(1)[0]

      ('A', 3)

      >>> counts.most_commont(1)[0][1]

      3

• 오른쪽 포인터는 계속 커지기 때문에 최댓값을 추출하기 위해서는 왼쪽 포인터는 0에서 움직이지 않는 게 가장 좋다.

  • 그렇지만, k연산 횟수를 넘어선다면 어쩔 수 없이 left += 1과 같이 왼쪽 포인터를 1 더 크게 한다.

• 마지막으로 최대 길이가 되는 값을 찾는다.

  • 오른쪽 포인터에서 왼쪽 포인터를 뺀 값이 가장 긴 길이가 되는 값이다.

  • 오른쪽 포인터는 가능한 한 크게하고, 왼ㅉ고 포인터는 가능한 한 작게 하는 값이 된다.

  • 이 부분은 생략이 가능하다.

    • 한 번 최댓값이 된 상태에서는 오른쪽 포인터가 한 칸 이동하면 왼쪽 포인터도 따라서 이동하게 되면서 max_len 값은 바뀌지 않기 때문이다.

    • 따라서 최댓값을 구하는 부분은 생략할 수 있다.

    • 이렇게 해서 실행 속도는 향상하였다. 하지만, 가독성이 줄어들었다.

      • 이처럼 가독성과 실행속도는 반비례인 관계가 종종 있으므로, 어느 경우를 택하든 많은 고민이 필요하다.