JavaScript에서 반복 문자가 포함된 문자열의 힘(Power) 찾기 — 최장 연속 문자 길이 구하기

문자열의 힘이란?

문자열의 힘(power)은 오직 하나의 고유한 문자로만 이루어진 비어 있지 않은 부분 문자열 중 가장 긴 길이를 의미합니다. 쉽게 말해, 같은 문자가 연속해서 반복되는 구간 중 최대 길이를 찾는 것이죠.

이번 글에서는 문자열을 인수로 받아 해당 문자열의 힘을 반환하는 자바스크립트 함수를 작성해 보겠습니다.

예시

예를 들어 다음과 같은 문자열이 있다고 가정해 봅시다.

const str = "abbcccddddeeeeedcba"

이 문자열에 대한 함수의 출력 결과는 5가 되어야 합니다.

그 이유는 부분 문자열 "eeeee"가 문자 'e'만으로 이루어져 있으며, 길이가 5로 전체 문자열에서 가장 긴 반복 구간이기 때문입니다.

해결 방법: 코드 구현

이 문제는 문자열을 한 번만 순회하면서 인접한 두 문자를 비교하면 됩니다. 두 문자가 같으면 카운트를 증가시키고, 다르면 카운트를 1로 초기화한 뒤, 지금까지의 최댓값을 계속 갱신해 주는 방식입니다.

const str = "abbcccddddeeeeedcba"

const maxPower = (str = '') => {
   let power = 1
   const sz = str.length - 1
   for(let i = 0; i < sz; ++i) {
      let count = 1
      while(i < sz && str[i + 1] === str[i] && ++i)
      power = Math.max(power, ++count)
   }
   return power
};

console.log(maxPower(str));

코드 설명

• power: 현재까지 발견된 최대 반복 길이를 저장하는 변수입니다. 모든 문자열에는 최소 한 개의 문자가 존재하므로 초기값은 1로 설정합니다.
• count: 현재 위치에서 시작되는 연속된 동일 문자의 개수를 세는 변수입니다.
• 바깥쪽 for문은 각 새로운 문자 그룹의 시작점을 탐색하고, 안쪽 while문은 같은 문자가 계속 반복되는 동안 인덱스를 이동시키며 count를 늘립니다.
• 매번 Math.max()를 호출하여 power 값을 갱신함으로써 최종적으로 가장 긴 반복 길이를 얻을 수 있습니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

5

시간 복잡도 및 공간 복잡도

이 알고리즘은 문자열 전체를 단 한 번 순회하므로 시간 복잡도는 O(n)입니다. 또한 별도의 추가 배열이나 맵을 사용하지 않으므로 공간 복잡도는 O(1)로, 매우 효율적인 해결책이라 할 수 있습니다.