Leet code (Medium): 424. Longest Repeating Character Replacement (슬라이딩 윈도우) - JAVA

 

 

하.. 이문제.. 방법을 알겠는데

슬라이딩 윈도우 알고리즘을 쓰면 된다. 간단히 시작점을 기억하는 방식.

흔히 조건을 만족하는 구간의 최대 길이를 구하는 문제에 활용되기 때문에, 이문제에서도 사용하면 된다.

윈도우 구간을 넓히면서 조건을 만족하지 않으면 start를 차차 뒤로 민다.

근데 이문제에서 이해가 안되는 부분이 있다.

 

start를 뒤로 밀 때, 난 윈도우 구간이 조건을 만족할 때까지 밀었다.

그래서 갯수가 가장 많은 알파벳의 갯수를 그때그때 업데이트 해줬다.

 

근데.. 그렇지 않아도 된다는 챗쥐피티의 답이 있었다.

윈도우 구간을 반드시 조건을 만족하도록 만들지 않아도 된다? 

왜그럴까.. 시간 복잡도가 생각보다 큰 차이가 없어서 일단 제출은 했지만 이유를 정확이 이해하지 못했다.

 

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int characterReplacement(String s, int k) {
        Map<Character, Integer> map = new HashMap<>();  // 문자 빈도를 저장하는 맵
        int maxCount = 0;  // 윈도우 내에서 가장 많이 등장한 문자 수
        int start = 0;     // 슬라이딩 윈도우의 시작점
        int maxLength = 0; // 가장 긴 동일 문자로 이루어진 문자열의 길이

        // 슬라이딩 윈도우를 확장
        for (int end = 0; end < s.length(); end++) {
            char currChar = s.charAt(end);
            map.put(currChar, map.getOrDefault(currChar, 0) + 1); // 문자 빈도 업데이트

            // 현재 윈도우에서 가장 많이 등장한 문자의 수 갱신
            maxCount = Math.max(maxCount, map.get(currChar));

            // (윈도우 크기) - (가장 많이 등장한 문자 수) > k 인 경우 윈도우 축소
            while (end - start + 1 - maxCount > k) {
                char startChar = s.charAt(start);
                map.put(startChar, map.get(startChar) - 1); // 시작 문자의 빈도 감소
                start++;  // 윈도우 시작점 이동
				
                // *** 시작 *** 이부분 안해도 된다함. 대체왜???????
                // 윈도우 축소 후, 다시 `maxCount`를 정확하게 갱신
                maxCount = 0;
                for (int value : map.values()) {
                    maxCount = Math.max(maxCount, value);
                }
                // *** 끝
            }

            // 최대 길이 갱신
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }
}