오늘은 릿코드 424번 문제 풀이(Longest Repeating Character Replacement)입니다.
이번 문제에서 구현해야 하는 함수는 두 개의 인자를 받습니다. 하나는 String(s), 하나는 integer(k) 인데요. 파라미터로 받은 스트링을 이용하여 만들 수 있는 모든 섭스트링에 대해 k만큼 알파벳을 바꿀 수 있을 때, 만들 수 있는 가장 긴 알파벳의 길이를 구하는 문제입니다.
예제를 한번 보겠습니다.
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.위의 경우 2번만큼 알파벳을 임의로 바꿀 수 있습니다.
모든 A를 B로 바꿀 수 있고, 반대로 B를 A로도 바꿀 수 있습니다. 두 경우 모두 'AAAA', 'BBBB'식으로 4번 연속으로 같은 문자가 나올 수 있으므로 리턴값은 4가 되게 됩니다. 밑에 설명이 되어 있지만, 입력값으로 들어오는 스트링은 영어 대문자로만 이루어져 있고, 길이는 1에서 1만 사이 입니다. k도 0보다 크거나 같고, 스트링의 길이보다 작거나 같아서 해당의 경우를 체크하는 로직은 건너뛰어도 무방합니다.
문제풀이
Two Pointer 이용
투포인터를 이용해서 풀어보았습니다. 투포인터라고 하면 Left와 Right를 써서 경우에 따라 포인터를 이동해 나가며 문제를 푸는 방법입니다. 미디움 문제의 경우 투포인터를 이용하는 경우가 꽤 있으니 참고하시면 좋을 듯 합니다.
먼저 알파벳 갯수만큼의 Frequency 맵(Array)을 만들어서 포인터 이동중에 알파벳을 추가해서 해당 지역(window)의 가장 긴 max를 업데이트 해 나가는 방식인 것을 말씀드리겠습니다.
우선 Left, Right 포인터 모두 0 인덱스로부터 시작하고, 카운트, 맥스, Frequency map을 모두 0으로 셋팅해줍니다.
let [left, right, mostFrequentCharCount, max] = new Array(4).fill(0);
const frequencyMap = new Array(26).fill(0);여기서 위 예제의 스트링과 넘버가 들어왔다고 합시다. 먼저 첫번째 인덱스부터 루프를 돌고, 루프 내에서는 로직이 끝나면 Right포인터를 옆으로 이동해줍니다. 이동된 Right포인터가 스트링의 길이보다 작을때까지 While루프를 이용해서 루프를 돕니다.
일단 코드부터 확인해 보겠습니다.
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var characterReplacement = function(s, k) {
let [left, right, mostFrequentCharCount, max] = new Array(4).fill(0);
const frequencyMap = new Array(26).fill(0);
while (right < s.length) {
const count = addRightFrequency(s, right, frequencyMap);
mostFrequentCharCount = Math.max(mostFrequentCharCount, count);
let window = right - left + 1;
const canSlide = k < window - mostFrequentCharCount;
if (canSlide) {
subtractLeftFrequency(s, left, frequencyMap);
left++;
}
window = right - left + 1;
max = Math.max(max, window);
right++;
}
return max;
};
const addRightFrequency = (s, right, map) => {
const char = s[right];
const index = getCode(char);
map[index]++;
return map[index];
};
const subtractLeftFrequency = (s, left, map) => {
const char = s[left];
const index = getCode(char);
map[index]--;
return map[index];
};
const getCode = (char) => char.charCodeAt(0) - 'A'.charCodeAt(0);여기서 addRight, subtractLeft, getCode 모두 헬퍼 펑션으로 주 함수 로직을 도와주는 함수입니다. 겟코드는 간단히 'A'는 0, 'Z'는 25와 같이 해당 문자에 맞는 인덱스를 리턴해 줍니다.
설명이 조금 난해할 수 있으니 이해하기 좀 더 수월한 예제를 들고 왔습니다.
Input: s = "ABABCXBBAA", k = 2| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| A | B | A | B | C | X | B | B | A | A |
이 코드에서 가장 중요한 부분은 맵이 만들어짐에 따라 정해지는 window와 canSlide를 이해하는 것입니다. window는 루프 안에서 R, L 포인터에 따른 해당 배열의 길이입니다. mostFrequentCharCount는 해당 루프에서 그려진 맵에서 최대로 빈도수가 높은 알파벳의 갯수입니다.
시간순으로 while루프 안의 변화를 살펴보겠습니다.
- 첫번째 루프
| 스트링 | Count |
| A | 1 |
- mostFrequentCharCount: 1
- window: 1
- 두번째 루프
| 스트링 | Count |
| A | 1 |
| B | 1 |
- mostFrequentCharCount: 1
- window: 2
- 세번째 루프
| 스트링 | Count |
| A | 2 |
| B | 1 |
- mostFrequentCharCount: 2
- window: 3
- 네번째 루프
| 스트링 | Count |
| A | 2 |
| B | 2 |
- mostFrequentCharCount: 2
- window: 4
네번째 루프까지 canSlide의 컨디션이 false가 되어 left포인터가 움직이지 않으면서 max의 값이 순차적으로 증가해 4가 되었습니다.
- 다섯번째 루프
| 스트링 | Count |
| A | 2 |
| B | 2 |
| C | 1 |
- mostFrequentCharCount: 2
- window: 5
- 다섯번째 루프에서 처음으로 canSlide 컨디션이 true가 되면서 같은 루프 내에서 맵에서의 변화가 일어났습니다.
- l: 1
-
스트링 Count A 1 B 2 C 1 - l은 왼쪽부터 시작한 포인터 이므로 가장 첫번째 인덱스의 알파벳인 A의 갯수를 하나 줄여주었습니다. max 의 값은 현재 루프에서의 배열의 길이가 되므로 l포인터가 1 증가하면서 4-1+1 = 4가 되어 max=4가 됩니다. 결과적으로 보면, r은 항상 한칸 이동하고, l도 컨디션에 따라 한칸 이동하면서, max는 루프를 도는 중 배열의 길이 중 가장 긴 것이 된다고 볼 수 있습니다.
이렇게 쭉 가다보면, 8번째 루프에서 4번 인덱스의 'C'와 5번 인덱스의 'X'를 바꾸는 것이 배열의 길이가 r(7) - l(3) + 1 = 5로 가장 길어진다는 것을 알 수 있습니다. C와 X를 바꾸면 B가 다섯번 등장하므로 맞는 정답이 됩니다.
Two Pointer 성능
- 시간복잡도: O(n)입니다. 하나의 와일루프를 사용했습니다.
- 공간복잡도: O(1)입니다. 배열의 갯수가 아닌, 제일 길게 생성된 배열의 길이가 알파벳의 갯수(26)만큼이 되기 때문입니다.
마지막으로 파이썬으로 풀었지만 이해에 도움이 될만한 영상을 첨부합니다.
※ 앞으로 모든 문제를 JavaScript 로 올릴 예정입니다. 릿코드 연습을 하며 올린 포스팅이므로 간혹 틀린 부분이 있을 수 있습니다. 혹시 잘못된 부분이 있을 경우 댓글 남겨주시면 감사드리겠습니다. 다른 문제 풀이도 깃헙에서 확인 할 수 있습니다.
댓글