시도한 풀이

시간초과로 오답

function splitString(s){
    if (s.length === 1) {
        return ''
    }
    const x = s[0];
    let xCount = 1;
    let notXCount = 0;
    let index 
    for (let i = 1; i < s.length; i++) {
        if (s[i] === x) {
            xCount++;
        }else{
            notXCount++;
        }
        if (xCount === notXCount) {
            index = i;
            break;
        }
    }
    if (index === undefined){
        return s
    }else{
        return s.slice(index+1)
    }
}

function solution(s) {
    var answer = 0;
    let str = s; 
    while (str.length > 0){
        str = splitString(str) 
        answer++;
    }
    
    return answer;
}

주어진 코드의 시간 초과 원인은 splitString 함수의 구조 때문입니다. 이 함수는 남은 문자열을 처음부터 다시 읽으며 반복적으로 분리 작업을 수행하는데, 전체 문자열 길이가 10,000일 때는 이 과정에서 비효율적입니다. 다음과 같은 부분에서 개선할 수 있습니다.

문제 분석 및 코드 개선 방안

1. 불필요한 문자열 복사:
   splitString 함수는 slice 메서드를 사용해 매번 새로운 문자열을 생성하고 리턴하는데, 이는 문자열을 복사해 반환할 때마다 O(n) 시간 복잡도를 발생시킵니다.

2. 반복적 접근 방식:
   전체 문자열을 반복해서 부분적으로 자르고 다시 splitString 함수로 넘겨주면서 문자열을 계속 잘라가는데, 이로 인해 O(n^2) 시간 복잡도가 발생하게 됩니다.

개선된 접근 방식

1. 문자열 한 번 순회:
   문자열을 처음부터 끝까지 한 번 순회하면서 주어진 규칙에 따라 x와 다른 문자의 개수를 실시간으로 카운트하고, 두 횟수가 같아질 때마다 바로 분리 카운트를 증가시키는 방법을 사용하면 됩니다.

2. 간단화된 로직:
   인덱스를 계속 이동하면서 x와 x가 아닌 문자를 카운트하고, 분리 지점에서 바로 분리 횟수만 증가시키는 형태로 구현합니다.

최적화된 코드

function solution(s) {
    let answer = 0;
    let xCount = 0;
    let notXCount = 0;
    let x = s[0];
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === x) {
            xCount++;
        } else {
            notXCount++;
        }
        
        // 두 횟수가 같아지면 분리
        if (xCount === notXCount) {
            answer++;
            // 다음 분리를 위해 초기화 및 새로운 x 설정
            xCount = 0;
            notXCount = 0;
            x = s[i + 1];
        }
    }
    
    // 남은 부분이 있을 경우 카운트 증가
    if (xCount !== 0 || notXCount !== 0) {
        answer++;
    }

    return answer;
}

개선된 코드 설명

1. 단일 순회:
   문자열을 한 번만 순회하며 필요한 값을 모두 계산하므로 시간 복잡도는 O(n)으로 줄어듭니다.

2. 불필요한 문자열 슬라이싱 제거:
   문자열을 슬라이스하거나 복사할 필요 없이 인덱스를 통해 탐색하므로 메모리 효율도 개선됩니다.

3. 남은 부분 처리:
   반복이 끝난 후에도 x와 x가 아닌 문자가 남아있는 경우 한 번 더 카운트를 증가시켜 최종 분리 개수를 정확히 반환합니다.