한 글자만 바꿔 만들 수 있는 가장 긴 동일 문자 구간
자바스크립트 코딩테스트 문제로 frequency-window 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문자열에서 최대 한 글자만 다른 문자로 바꿀 수 있을 때, 같은 문자만으로 이루어진 가장 긴 연속 구간의 길이를 구하세요.
예를 들어 "AABABBA"에서는 한 글자를 바꿔 "AAAA" 같은 길이 4 구간을 만들 수 있습니다.
제한사항
1 <= s.length <= 100,000s는 영어 대문자로만 이루어집니다.- 한 글자를 바꾸지 않아도 됩니다.
- 반환값은 만들 수 있는 가장 긴 동일 문자 연속 구간의 길이입니다.
예시
- 입력:
"AABABBA"→ 출력:4 - 입력:
"AAAA"→ 출력:4 - 입력:
"ABCD"→ 출력:2 - 입력:
"BAAAC"→ 출력:4
힌트
- 어떤 구간 안에서 가장 많이 등장한 문자를 기준으로 생각해 보세요.
- 현재 구간 길이에서
가장 많이 나온 문자 개수를 빼면, 바꿔야 하는 문자 수를 알 수 있습니다. - 바꿔야 하는 문자가 2개 이상이 되면 왼쪽 경계를 줄여야 합니다.
해설
슬라이딩 윈도우로 현재 연속 구간 후보를 관리합니다.
구간 안에서 가장 많이 나온 문자의 개수를 maxFreq라고 하면,
이 구간을 전부 같은 문자로 만들기 위해 바꿔야 하는 글자 수는:
구간 길이 - maxFreq
입니다.
우리는 최대 한 글자만 바꿀 수 있으므로,
이 값이 1 이하인 구간만 유효합니다.
따라서 오른쪽 포인터를 한 칸씩 늘리면서 문자 빈도를 세고,
구간 길이 - maxFreq > 1 이 되는 순간 왼쪽 포인터를 이동시켜 구간을 다시 줄입니다.
그 과정에서 만들 수 있는 최대 구간 길이를 계속 갱신하면 됩니다.
예를 들어 "BAAAC"를 보면:
"BAAA"구간에서는A가 3개이므로 1글자만 바꾸면 전부 같은 문자로 만들 수 있습니다.- 길이 4가 가능하므로 정답 후보는 4입니다.
"BAAAC"전체는 길이 5인데 가장 많이 나온 문자는A3개뿐이라 2글자를 바꿔야 해서 불가능합니다.
이 방식은 문자열을 한 번 훑으면서 처리할 수 있어 시간 복잡도는 O(n)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
JavaScript
에디터 로딩 중...
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
아직 실행하지 않았습니다.
실행 결과
아직 실행하지 않았습니다.
예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.