알고리즘 65번 - 문자열 나누기

URL : https://school.programmers.co.kr/learn/courses/30/lessons/140108

JS

문제

문제 설명
문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.

먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간(?) 멈추고, 지금까지 읽은 문자열을 분리합니다.
s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.
만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.
문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.

제한사항
1 ≤ s의 길이 ≤ 10,000
s는 영어 소문자로만 이루어져 있습니다.
입출력 예
s                                 result
"banana"                    3
"abracadabra"            6
"aaabbaccccabba"     3
입출력 예 설명
입출력 예 #1
s="banana"인 경우 ba - na - na와 같이 분해됩니다.

입출력 예 #2
s="abracadabra"인 경우 ab - ra - ca - da - br - a와 같이 분해됩니다.

입출력 예 #3
s="aaabbaccccabba"인 경우 aaabbacc - ccab - ba와 같이 분해됩니다.

 

---

계획

1.첫글자와 같은 알파벳이 나온 수를 카운트

2.첫글자와 다른 알파벳이 나온 수를 카운트

3. 1,2가 같은 수가 나오면 문자열s에서 분리. (stringDecomposition 배열 만들어서 넣기)

4. 남은 s에서 동일과정 반복

5.진행할 문자가 없으면 s에서 분리하고 종료

6. 분리된 문자열을 반환( stringDecomposition  배열의 길이)

---

참고, 풀이

function solution(s) {
    let count = 0;
    const x = s[0];
    let string = s;
    while (string.length > 0) {
        let [same, difrent] = [0, 0];
        for (let i = 0; i < string.length; i++) {
            // 1.첫글자와 같은 알파벳이 나온 수를 카운트
            if (x === string[i]) {
                same++;
            }
            // 2.첫글자와 다른 알파벳이 나온 수를 카운트
            if (x === string[i]) {
                difrent++;
            }
            // 3. 1,2가 같은 수가 나오면 문자열s에서 분리.
            if (same > 0 && same === difrent) {
                count++;
                string = string.slice(i + 1); // 동일한순간까지의 문자열
            }
            if (i > 0 && i === string.length - 1) {
                count++; // 꺼내기
                string = string.slice(i + 1);
            } 
        }
        // (stringDecomposition 배열 만들어서 넣기)
    }
    return count;
}

x가 분리한 문자열의 첫번째여야 하는데 그냥 처음받은 문자열 앞문자로 고정했었네....

---

답

function solution(s) {
    let count = 0; // 분리된 문자열 개수
    let i = 0; // 문자열의 현재 인덱스

    while (i < s.length) {
        let same = 0, different = 0; // 같은 글자와 다른 글자의 카운트
        const x = s[i]; // 현재 문자열의 첫 글자
        
        // 현재 문자열을 탐색하면서 조건을 만족하는 곳에서 분리
        while (i < s.length) {
            if (s[i] === x) {
                same++;
            } else {
                different++;
            }
            
            i++; // 다음 문자로 이동
            
            // 같은 글자와 다른 글자의 수가 같아지면 분리
            if (same === different) {
                break;
            }
        }
        
        count++; // 분리된 문자열 개수 증가
    }
    
    return count;
}

코드 간략화하기

function solution(s) {
    let count = 0, i = 0;

    while (i < s.length) {
        let [same, different] = [0, 0];
        const x = s[i];

        while (i < s.length) {
            s[i] === x ? same++ : different++;
            i++;
            if (same === different) break;
        }
        count++;
    }

    return count;
}

다른사람 답

function solution(s) {
    let count = 0;

    for (let i = 0; i < s.length;) { // i++은 조건문 안에서 처리
        let same = 0, different = 0;
        const x = s[i];
        
        for (; i < s.length; i++) {
            if (s[i] === x) {
                same++;
            } else {
                different++;
            }
            
            if (same === different) {
                i++; // 조건 충족 시 탐색 위치 갱신
                break;
            }
        }
        count++; // 분리된 문자열 개수 증가
    }
    
    return count;
}

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

    for(let i = 0; i < s.length; i++) {
        if(count === 0) { // 첫 문자와 같은수와 다른 수가 동일 할 때
            answer++; // 끊은 문자열 개수
            current = s[i] // 비교값 문자열 첫문자
            count = 1
        } else {
            if(current !== s[i]) count--; // 다르면 -1
            else count++; // 같으면 +1
        }
    }

    return answer;
}

---

참고