[99클럽] 코딩테스트 스터디, 3일차 TIL - 비기너

 

1. 문제풀이

1) 문제 : 문자열 나누기, 프로그래머스

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

 

- 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.

- 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다.

- 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.

- s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.

- 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.

 

문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.

 

제한사항

- 1 ≤ s의 길이 ≤ 10,000 

- s는 영어 소문자로만 이루어져 있습니다.

 

입출력 예 설명

- s="banana"인 경우 ba - na - na와 같이 분해됩니다.

- s="abracadabra"인 경우 ab - ra - ca - da - br - a와 같이 분해됩니다.

 

 

2) 해석

- 첫 글자 = x

- sameCnt = x와 같은 문자 횟수, differentStr = x와 다른 문자 횟수

- sameCnt === differentCnt && cnt++

- 그다음 문자열부터 다시 반복

- 더 이상 읽을 글자가 없다면, 지금까지 읽은 문자열을 분리하고 종료

 

 

3) 풀이

function solution(s) {
    let cnt = 1;  
    let repeatStr = s;
    
    function helper (repeatStr){
        const len = repeatStr.length;
        const x = repeatStr[0];
        
        let sameCnt = 1;
        let differentCnt = 0;
        
        if(len === 0) return cnt;
        
        for(let i=1; i < len; i++){            
            if(sameCnt === differentCnt) {
                cnt++
                return helper(repeatStr.slice(i))
            } 
            
            if(repeatStr[i] === x) sameCnt++
            else differentCnt++
        }
    }
    
    helper(repeatStr)
    
    return cnt;
}

 

계속해서 반복 실행하라는 텍스트를 보고 재귀함수를 사용했다. 

사실 다른 방식이 있을지도 모른다는 생각을 하긴 했는데, 30분이라는 제한시간이 있었기 때문에 가장 먼저 떠오른 방법을 사용했다. 

 

 

let cnt = 1;  
let repeatStr = s;

 

우선 재귀함수 바깥쪽에 cnt와 repeatStr를 정의해 줬다.

cnt는 분해된 문자열의 개수를 의미하며, repeatStr는 재귀함수에 넣을 문자열을 의미한다.

 

첫 글자를 넣는 순간 하나로 분해되기 때문에 cnt의 기본 값을 1로 지정했다.

repeatStr의 경우, 해석한 것을 보고 따로 분리해 놓기 위해 지정했었는데 다시 생각 보니 굳이 지정하지 않아도 될 것 같다.

 

function helper(repeatStr){
    const len = repeatStr.length;
    const x = repeatStr[0];
        
    let sameCnt = 1;
    let differentCnt = 0;
        
    if(len === 0) return cnt;
    ...
}

 

그 후 helper 함수를 만들었다.

x 변수에 문자열의 제일 처음 값을 저장해 줬다.

 

그리고 sameCnt, differentCnt 변수를 만들어줬다.

여기서 sameCnt는 x와 같은 값의 횟수가 들어가고, differentCnt에는 x와 다른 값에 횟수가 들어간다.

이미 x가 분해되어 있으므로 sameCnt는 기본값을 1로 지정해 줬다. 

 

더 이상 문자열이 없다면, 재귀함수에서 return 돼야 하므로 조건문으로 넣어줬다. 

 

 

for(let i=1; i < len; i++){            
    if(sameCnt === differentCnt) {
        cnt++
        return helper(repeatStr.slice(i))
    } 
               
    if(repeatStr[i] === x) sameCnt++
    else differentCnt++
}

 

이제 for문을 사용해 len의 길이만큼 반복문을 돌려줬다.

 

sameCnt와 differentCnt가 같다면, cnt에 1을 추가하고 slice를 이용해 해당 인덱스부터 문자열을 새로 만들어 재귀함수를 호출했다.

해당 문자의 값과 x의 값이 같다면, sameCnt++을 그렇지 않다면 differentCnt++을 해줬다.

 

 

- 걸린 시간

 

 

2. 리팩토링

 

코드를 설명해면서 느낀 건데, 좀 복잡하고 반복문 안에서 slice가 실행되는 게 마음에 안 들었다. 

재귀를 사용해서 그런지 성능이 좋지 않다는 생각이 들었다.

 

다른 사람들 코드를 보니 대부분 재귀를 사용하지 않은 거 같아서 재귀를 사용하지 않고 짜는 방법을 생각해 봤다.

 

function solution(s) {
    let cnt = 0;
    let sameCnt = 0;   // 같으면 + 다르면 -하기, 0이면 cnt++
    let x;
    
    for(let i=0; i<s.length; i++){
        if(sameCnt === 0) {
            cnt++;
            x = s[i];
            sameCnt = 1
        } else {
            if(s[i] === x) sameCnt++
            else sameCnt--
        }
    }
    return cnt;
}

 

해당 문제의 포인트는 sameCnt와 differentCnt가 같다면, 그다음 문자부터 비교를 시작하는 것이다.

따라서 굳이 재귀를 사용해서 문자열을 다시 비교하지 않아도 된다.

 

sameCnt와 differentCnt도 굳이 나눌 필요 없다.

하나의 변수를 만든 후, 값이 같으면 + 다르면 -를 해서 0이 되는 경우를 찾으면 되기 때문이다.

따라서 sameCnt 하나만 만들어줬다.

 

그 후 x 변수를 선언해 준다. 

x 변수는 현재 비교해야 하는 문자를 의미한다.

 

for문을 이용해 s.length만큼 문자열을 반복해 준다.

 

sameCnt가 0이 되면, 문자열을 다시 처음부터 비교해야 하므로 조건문을 넣어준다.

우선, cnt의 값을 증가시켜 주고, x의 값을 s[i]로 지정해 준다.

이때 문자열이 이미 하나 나눠진 것이므로 sameCnt의 값일 1로 지정해 준다.

 

그리고 sameCnt가 0이 아닐 경우, s[i]와 x를 비교해 sameCnt의 값을 증가 혹은 감소시켜 준다.

 

 

기존의 재귀함수의 경우, 시간 복잡도가 O(n^2)였는데, 위 방식으로 풀이하면 O(n)으로 줄어든다.

처음부터 위 방식으로 생각하면 좋았을 텐데 반복이라는 것에 꽂혀서 바로 재귀로 시작한 점이 조금 아쉽다.

 

예전에 멘토링받았을 때, 코딩테스트는 무조건 많이 풀어봐야 감이 온다는 말을 들은 적이 있다.

이제 막 시작하는 것이기 때문에 아쉬움은 그만하고 다른 방식으로 생각하는 것에 익숙해지도록 노력해야겠다!