프로그래머스 L1 - 문자열 나누기

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

프로그래머스

X를 기준으로 X의 갯수와 나머지 다른 문자의 갯수가 동일해지는 시점에서 문자열을 자른다.

그렇게 해서 잘린 문자열의 갯수를 반환하는 문제이다.

 

function solution(s) {
    let x = 0;
    let cnt = 0;
    let ret = [];
    for(let i = 0; i<s.length; i++){
        if(s[i]===s[x]) cnt++;
        else cnt--;
        if(cnt===0){
            ret.push(s.substring(x,i+1));
            x = i+1;
        }
    }
    if(ret.join("").length === s.length) return ret.length;
    return ret.length+1;
}

X와 문자가 같다면 cnt를 하나씩 늘려주고, 다르다면 cnt를 하나씩 뺀다.

cnt가 0이 되는 지점이 바로 X의 갯수와 다른 문자의 갯수가 동일해지는 시점이다.

그 시점에서 substring 메서드를 이용해서 문자열을 자르고 ret 배열에 넣는다.

그리고 ret 배열의 요소를 합쳤을 때 s의 길이와 같은지 비교한다.

만일 banana 같은 문자열이면 ret 배열의 요소를 합쳤을 때, banana가 나오고 이는 s의 길이와 동일하다.

이럴 때는 바로 ret의 길이를 리턴하면 된다.

하지마 abracadabra 같은 문자열은 ret 배열의 요소를 합쳤을 때 abracadabr 까지만 합쳐지므로 s와 길이가 다르다.

이 경우는 X와 다른 문자와의 횟수가 다른 경우이면서 더 이상 읽을 문자열이 없는 경우이다.

이럴때는 지금까지 읽은 문자열을 분리해야하므로 ret의 길이에 1을 더해준 다음 리턴한다.

 

사실 이 문제는 재귀로 접근하려고 했다.

하지만 막상 구현하려고 하니 어려워서 구현하지 못했다.

다른 분께서 재귀로 구현한 코드를 보고 대단하다는 생각이 들었다.

function solution(s, count=0) {
    if(!s) return count
    let [first, ...rest] = s.split("")
    let countSame = 1
    let countInSame = 0
    let i=0
    for(; i<rest.length; i++){
        if(rest[i] === first) countSame++
        else countInSame++
        if(countSame === countInSame) break
    }
    return solution(rest.slice(i+1).join(""), count+1)
}

먼저 재귀는 같은 로직이 반복되면서 매개변수가 달라지는 경우에 활용할 수 있다.

이 로직은 탐색할 문자열과 나눠진 문자열의 갯수가 변경된다.

X와 나머지 요소를 구분해서 X의 갯수와 나머지 문자의 갯수가 동일해지는 시점에 반복문을 종료한다.

그리고 탐색할 문자열을 분리한 문자열을 제외한 나머지 문자열로 변경하고 갯수를 하나 늘려준다.

기저 조건은 더 이상 탐색할 문자열이 없다면 그대로 카운트를 리턴하면 된다. 

그렇다면 모든 재귀 함수들이 마지막 호출한 것부터 하나씩 리턴되면서 분리된 문자열의 갯수를 반환한다.