Leetcode 424. Longest Repeating Character Replacement (Java 풀이) - Sliding Window

URL : https://leetcode.com/problems/longest-repeating-character-replacement/description/

LeetCode - The World's Leading Online Programming Learning Platform

안녕하세요, 오늘은 Leetcode의 424번 문제, Longest Repeating Character Replacement에 대해서 알아보겠습니다!

 

먼저 문제의 내용은 다음과 같습니다.

문제를 읽어 본 다음에, 문제에 대해서 천천히 이해해보는 시간을 가지도록 하죠!

 

1. 문제 상황 이해

 '너는 k 개수만큼의 알파벳을 다른 알파벳으로 교체할 수 있다. 이 때, 주어진 문자열 중에서 동일한 문자로 구성되는 부분 문자열 중 가장 긴 부분 문자열의 길이를 구해라"

 

- 주어진 문자열 s가 "ABAB"이고, 주어진 k가 2일 때

s에 등장하는 두 개의 B를 A로 바꾸면! "AAAA"라는 4글자의 repeating substring이 나오게 되고, 따라서 이 경우 정답은 4가 됩니다.

 

- 주어진 문자열 s가 "AABABBA"이고, 주어진 k가 1일 때

세 번째에 등장하는 B를 A로 바꾸면! "AAAABBA"라는 문자열이 만들어 지고, 이경우 repeating substring의 길이는 4가 됩니다.

 

2. 아이디어

 

 '가장 긴 부분 문자열', '가장 합이 큰 부분 배열'이라는 단어가 나오면 보통 슬라이딩 윈도우를 통해 해법을 찾을 수 있는 알고리즘 문제입니다. 슬라이딩 윈도우와 투 포인터를 구분해서 정의하는 경우도 있기는 하지만, 슬라이딩 윈도우나 투 포인터나 양 끝에 두 포인터를 두고, 포인터 내부에 갇혀 있는 배열의 원소를 통해 연산과 풀이를 진행한다는 공통점이 있기 때문에 따로 구분을 하지 않기도 합니다. 

 

 

 이 문제의 핵심 아이디어는 다음 정도가 될 것입니다.

 

 (n + m) 크기의 윈도우 내에 가장 많은 수를 차지하고 있는 알파벳을 'A'라고 해 보자.

 윈도우 내에 알파벳 'A'가 n개 존재한다면, 'A'가 아닌 알파벳이 m개 존재하는 것이다.

 이 m의 값이 k보다 작거나 같다면, 이 윈도우를 통해 최장 n + m 길이의 부분 문자열을 구성할 수가 있다. 

 

왜냐하면 'A'가 아닌 다른 모든 m개의 원소들을 'A'로 교체할 수가 있기 때문입니다.

 

3. 전체 소스 코드

class Solution {

	// 슬라이딩 윈도우 내에 가장 많이 등장하는 알파벳이 무엇인지를 반환한다.
    public int getMaxFrequent(int[] freq) {
        int m = 0;
        for(int f : freq)
            m = Math.max(f, m);
        return m;
    }

    public int characterReplacement(String s, int k) {
        int maxLength = 0;
        
        // 슬라이딩 윈도우 내에 존재하는 알파벳의 개수를 세기 위한 배열이다.
        // 자주 사용되는 트릭이니 code sniffet으로 만들어 둘 것!
        int[] freq = new int[26];

		// l은 슬라이딩 윈도우의 좌측 경계
        // r은 슬라이딩 윈도우의 우측 경계
        for(int l = 0, r = 0; r < s.length(); r++) {
        
        	// 슬라이딩 윈도우의 우측 경계를 우측으로 이동시키면서 알파벳에 대한 연산을 진행한다
            char ch = s.charAt(r);
            freq[ch-'A']++;

            int maxCount = getMaxFrequent(freq);
            
            // 만약 슬라이딩 윈도우 내에 가장 많이 등장하는 글자와 슬라이딩 윈도우 길이의 차이가
            // k보다 크다면, 슬라이딩 윈도우 부분을 최장 반복수열로 구성할 수 없다는 의미이다.
            // 이러한 상황에서는 슬라이딩 윈도우의 좌측을 오른쪽으로 옮긴다!
            while(r - l + 1 - maxCount > k) {
                freq[s.charAt(l) - 'A']--;
                l++;
            }

			// 슬라이딩 윈도우를 옮길 때마다 최장 반복수열 길이를 갱신하기
            maxLength = Math.max(maxLength, r - l + 1);
        }   

        return maxLength;
    }
}