[Javascript] 프로그래머스 - 문자열 나누기

문제 설명

주어진 문자열 s를 특정 규칙에 따라 여러 문자열로 분해하는 문제입니다.
문자열을 왼쪽에서 오른쪽으로 순차적으로 탐색하며, 첫 번째로 등장하는 문자를 x로 정합니다. 이후 x와 x가 아닌 문자의 등장 횟수를 각각 세면서, 두 횟수가 같아지는 순간 문자열을 분리합니다.
이 과정을 문자열 전체에 대해 반복하여, 최종적으로 분해된 문자열의 개수를 구합니다.

---

제한 사항

• 1 ≤ s의 길이 ≤ 10,000
• s는 영어 소문자로만 이루어져 있습니다.

---

해결 방법

• 알고리즘: 그리디, 문자열 탐색
• 문자열을 순차적으로 탐색하면서 첫 번째로 등장하는 문자를 기준(x)으로 설정
• x의 개수와 x가 아닌 문자 개수를 카운트
• 두 개수가 같아질 때 문자열을 분리하고, 새로운 기준 문자를 설정하여 반복

---

시간 복잡도

• 문자열을 한 번 순회하므로 O(N)

---

구현 코드

function solution(s) {
  let answer = 0;
  let count = 0;
  let base = "";

  for (const char of s) {
    base ||= char;

    count += char === base ? 1 : -1;

    if (count === 0) {
      ++answer;
      base = "";
    }
  }

  if (base) ++answer;

  return answer;
}