🟠[Leet code - 424] Longest Repeating Character Replacement ✅

 

Longest Repeating Character Replacement - LeetCode

문제

• Input
  문자열 s, 정수 k
• Output
  문자열 s에서 최대 k개의 문자를 다른 문자로 바꿀 수 있을 때,
  모든 문자가 같은 문자로 이루어진 가장 긴 부분 문자열의 길이를 반환.

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

| O(1) : 크게 상관 없음 | O(log n) : 크게  상관 없음 | O(n) :  100'000'000 (1억) | O(n log n) : 1'000'000 (100만) | O(n^2) : 10'000 (1만) |

---

 

$1  \le n \le 100'000$로 $O(n^2)$은 불가능하고, $O(n \log n)$부터 고려해 볼 수 있다.

 

 

해결 과정

먼저 최대 k번 문자를 교체한다는 뜻은, 무조건 k번사용하는 게 아니라고 생각했다.

그렇다는 것은, 어떤 걸 기준으로 삼아서 0 ~ k 까지 반복하는 게 아닐까?라고 생각이 들었다.

 

그 기준이 될 수 있는게 뭐가 있을까 생각하다가 A부터 Z까지 알파벳 하나하나 될 수 있다고 생각했고,

각 알파벳마다 문자열을 순회하며 0 ~ k번의 문자교체를 확인하면서 최대 값을 찾아가면 되지 않을까라고 생각했다.

시간이야 대략 $26 \times 100'000$이니까 괜찮을거라고 생각했다.

 

좀 더 구체적으로 고민하다가 0 ~ k번의 문자교체를 투 포인터형식으로 가져가면 모든 문제교체의 경우의 수를 보지 않아도,

항상 최적의 k값을 통하여 최대 길이를 확인할 수 있을것 같았다.

그럼 시간은 $25 \times 100'000 * 2$로 충분히 통과 가능한 시간이기에 해당 방법으로 진행했고, 아래와 같은 수도 코드를 작성했다.

int ret = 0;
for (char alp = 'A'; alp <= 'Z'; ++alp)
{
    int l = 0;
    int useK = 0;

    for (int r = 0; r < s.size(); ++r)
    {
        IF s[r]가 alp와 다르면 useK 증가

        WHILE useK가 k보다 크면
        {
            IF s[l]가 alp와 다르면 useK 감소
            l 증가
        }

        현재 길이 (r - l + 1)로 ret 갱신
    }
}

return ret;

 

 

구현

int characterReplacement(string s, int k) 
{
    int ret = 1;
    
    for (char alp = 'A'; alp <= 'Z'; ++alp)
    {
        int l = 0;
        int useK = 0;
        for (int r = 0; r < s.size(); ++r)
        {
            if (alp != s[r])
            {
                while (k < ++useK)
                    if (s[l++] != alp) --useK;
            }
            
            ret = std::max(ret, r - l + 1);
        }
    }

    return ret;
}

 

 

개선 코드

내 풀이보다 더 빠른 풀이가 존재한다.

간단하게 설명하면, 현재 윈도우 안에서 가장 많이 등장한 문자 개수를 이용하면, 알파벳을 하나씩 직접 고정하지 않고도 한 번의 순회로 답을 구할 수 있었다.

그렇기 때문에 시간복잡도는 O(n)을 가진다.

 

내가 사용했던 변수 useK를 현재 윈도우 길이 - 많이 등장한 알파벳 개수로 계산을 하였고,

useK가 k보다 많다면, Left를 이동한다. 이 부분이 내 코드와의 핵심적인 차이 같다.

int characterReplacement(string s, int k) 
{
    vector<int> freq(26, 0);
    int left = 0;
    int maxFreq = 0;
    int answer = 0;

    for (int right = 0; right < s.size(); ++right) {
        maxFreq = max(maxFreq, ++freq[s[right] - 'A']);

        while ((right - left + 1) - maxFreq > k) {
            --freq[s[left] - 'A'];
            ++left;
        }

        answer = max(answer, right - left + 1);
    }

    return answer;
}

 

 

되돌아보기

내가 개선된 코드로 풀이를 하기위해서는, '어떤 값을 기준으로 고정하여 0 ~ k를 확인' 이런 사고에서 한 번 더 생각하여 '굳이 그 문자를 고정할 필요가 있나?'까지 가면 좋았을 듯? 하다.

슬라이딩 윈도우를 좀 풀어보고 있는데, 뭔가 윈도우 내에서 최적의 값을 이용하는 문제가 많은 것 같다.

 

아무튼 그래서 여러 기준을 직접 나누어 보는 풀이를 생각했다면,
그 기준들을 하나의 상태값으로 합칠 수는 없는지 한 번 더 생각해 봐야겠다.