[LeetCode]Longest Repeating Substring With Replacement

이 문제는 문제를 이해하는 것만으로도 한참 걸렸다. 그래서 GPT한테 물어봄

아하 오키 이해완료. 그럼 어떻게 알고리즘을 짜야할까?

첫 접근

뭔가 s문자열을 하나씩 돌다가 이전 글자와 다른 문자를 만났을 때 if문으로 빼서 그 다른 글자를 이전 글자로 바꾸고(그런데 s[0]의 -1은 맨 마지막 글자니까 그것마 빼고), 그 횟수를 ++시켜서 k랑 비교할때 res의 길이를 반환하면 되겠다!! 싶었음. 그래서 짠. 코드가 이거.. 하지만 엄청나게 많은 문법적 오류가 있었고..ㅋㅋㅋㅋㅋㅋ(이것저것 주워 듣기만 한 자의 폐혜) GPT가 고쳐줌.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        res = []
        for i in s:
            j=0
            res.append(s[i])
            if i > 0 and s[i] != s[i-1]:
                s[i] = s[i-1]
                j += 1
            elif j == k :
                return res.length

그렇게 GPT가 수정해준 내 알고리즘 코드

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        res = []  # 결과 리스트
        j = 0  # 문자 변경 횟수
        
        # 인덱스 기반으로 문자열을 순회
        for i in range(len(s)):
            res.append(s[i])  # 문자를 결과 리스트에 추가
            
            # i > 0일 때, 현재 문자와 이전 문자를 비교
            if i > 0 and s[i] != s[i-1]:
                # 문자열은 불변이므로 수정 불가, 리스트로 변환 후 수정 가능
                # 수정 대신 교체 횟수 증가
                j += 1
            
            # 교체 횟수가 k에 도달했을 때
            if j == k:
                return len(res)  # 현재까지의 리스트 길이를 반환
        
        return len(res)  # 전체 리스트 길이를 반환

내 코드랑 다른점
1. 인덱스 기반으로 for문을 돌림. --> range(len(s))로 숫자로서 접근하면됨.
2. 문자열은 수정안됨...(어차피 우린 길이만 반환하면 되는거였으니까 쓸모없긴했음..)

그런데, 오류남!!!

모르겠다. 해결책을 주세요
해결책:

• 이 문제는 슬라이딩 윈도우와 빈도 카운팅을 사용하여 해결하는 것이 적합합니다.
• 문자열에서 동일한 문자를 기준으로 다른 문자를 변경하면서, 가장 긴 부분 문자열을 찾는 방식으로 접근해야 합니다.

--> 그냥 알고리즘 자체가 잘못되었다. 전체 문자열 중에 가장 많은 알파벳을 뽑아서 그걸 기준으로 했어야함.

ChatGPT가 준 슬라이딩 윈도우 코드

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}  # 각 문자의 빈도를 저장하는 딕셔너리
        maxf = 0  # 현재 윈도우에서 가장 빈도가 높은 문자 수
        l = 0  # 슬라이딩 윈도우의 왼쪽 포인터
        res = 0  # 결과 값 (가장 긴 부분 문자열 길이)

        # 오른쪽 포인터로 문자열을 순회
        for r in range(len(s)):
            # 현재 문자의 빈도를 증가시킴
            count[s[r]] = count.get(s[r], 0) + 1
            # 가장 많이 등장한 문자의 빈도를 갱신
            maxf = max(maxf, count[s[r]])

            # (현재 윈도우 크기) - (가장 빈도 높은 문자 수) > k 이면 왼쪽 포인터 이동
            if (r - l + 1) - maxf > k:
                count[s[l]] -= 1  # 왼쪽 포인터가 가리키는 문자의 빈도 감소
                l += 1  # 왼쪽 포인터 이동

            # 최대 길이 갱신
            res = max(res, r - l + 1)

        return res  # 결과 반환

그럼 질문!!
딕셔너리에다가 A:3, B:2 이런 형태로 저장할거 아닌가 그럼 그냥 딕셔너리에 다 저장해놓고 가장 빈도가 높은 문자수를 구하면 되는거아닌가? 라고 생각했는데..
아니다, 그렇게 되면 매번 딕셔너리를 순회하면서 가장 많이 등장한 문자를 찾아야 하기 때문에 비효율적이라고 한다.

그렇구나.. 그래서 코드를 이해해보고 나름대로 그려보면..

오키.. 일단 이해는 했다. 다음에 응용문제 나왔을때 꼭 기억해보자..