[Algorithm] 문자열 나누기

문제 설명

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

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

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

 

문제풀이

1. [반복문] 문자열 배열 크기만큼 순회한다.
   1. 현재 알파벳 값을 저장한다.
   2. 현재 알파벳의 개수와 다른 알파벳의 개수를 0으로 초기화한다.
   3. [반복문] 현재 문자부터 배열 크기만큼 순회한다.
      1. 현재 문자와 동일하다면 현재 알파벳 개수를 증가한다.
      2. 그렇지 않다면 다른 알파벳 개수를 증가한다.
      3. 현재 알파벳 개수와 다른 알파벳 개수가 동일하다면 반복문을 멈춘다.
   4. 결과값을 1증가시킨다.
2. 결과값을 반환한다.

 

코드 작성

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    for (int idx = 0; idx < s.size();)
    {
        char curAlpha = s[idx];
        int curAlphaCount = 0;
        int otherAlphaCount = 0;
        
        int nextIdx = idx;
        while (nextIdx < s.size())
        {
            if (curAlpha == s[nextIdx])
            {
                ++curAlphaCount;
            }
            else
            {
                ++otherAlphaCount;
            }
            
            if (curAlphaCount == otherAlphaCount)
            {
                break;
            }
            nextIdx++;
        }
        idx = nextIdx + 1;
        answer++;
    }
    
    return answer;
}