[프로그래머스][C++] 문자열 나누기

문자열 나누기

문제 링크

문자열 나누기

분석

문자열을 왼쪽에서부터 오른쪽으로 읽어나가며, 특정 조건을 만족한다면 부분 문자열을 나눕니다.

여기서 특정 조건은 첫 번째 문자와 같은 문자의 개수와 다른 문자의 개수가 같아지는 순간입니다.

부분 문자열을 나누고 남은 문자열이 있다면 같은 방법으로 계속 분해합니다.

끝까지 확인했다면 나누어진 문자열의 개수를 반환합니다.

풀이

#include <string>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    // 첫 번째 문자 저장
    char key = 0;
    // 첫 번째 문자의 개수
    int xCount = 0;
    // 첫 번째 문자 이외의 개수
    int otherCount = 0;
    for (int i = 0; i < s.length(); ++i)
    {
        // key가 초기화되지 않았다면 현재 문자로 설정
        if (key == 0)
        {
            key = s[i];
        }
        
        // key와 현재 문자가 같은지 확인하고 개수 증가
        (key == s[i]) ? ++xCount : ++otherCount;
        
        // 첫 번째 문자의 개수와 다른 문자들의 개수가 같은 경우
        if (xCount == otherCount)
        {
            ++answer;
            key = 0;
            xCount = 0;
            otherCount = 0;
        }
    }
    
    // 루프 종료 후 아직 처리되지 않은 문자열이 있는 경우
    if (key != 0)
    {
        ++answer;
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• s를 순회하는 반복문 $O(n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 4.13MB)
테스트 2 〉 통과 (0.03ms, 3.68MB)
테스트 3 〉 통과 (0.03ms, 4.19MB)
테스트 4 〉 통과 (0.01ms, 4.14MB)
테스트 5 〉 통과 (0.01ms, 4.2MB)
테스트 6 〉 통과 (0.01ms, 4.19MB)
테스트 7 〉 통과 (0.01ms, 4.19MB)
테스트 8 〉 통과 (0.01ms, 4.2MB)
테스트 9 〉 통과 (0.02ms, 4.2MB)
테스트 10 〉 통과 (0.05ms, 4.16MB)
테스트 11 〉 통과 (0.01ms, 4.2MB)
테스트 12 〉 통과 (0.02ms, 4.14MB)
테스트 13 〉 통과 (0.04ms, 4.21MB)
테스트 14 〉 통과 (0.04ms, 4.21MB)
테스트 15 〉 통과 (0.01ms, 4.26MB)
테스트 16 〉 통과 (0.03ms, 4.13MB)
테스트 17 〉 통과 (0.02ms, 4.21MB)
테스트 18 〉 통과 (0.03ms, 4.14MB)
테스트 19 〉 통과 (0.02ms, 4.21MB)
테스트 20 〉 통과 (0.03ms, 4.21MB)
테스트 21 〉 통과 (0.04ms, 4.2MB)
테스트 22 〉 통과 (0.02ms, 4.19MB)
테스트 23 〉 통과 (0.01ms, 4.2MB)
테스트 24 〉 통과 (0.02ms, 4.21MB)
테스트 25 〉 통과 (0.06ms, 3.66MB)
테스트 26 〉 통과 (0.03ms, 4.2MB)
테스트 27 〉 통과 (0.03ms, 4.2MB)
테스트 28 〉 통과 (0.03ms, 4.2MB)
테스트 29 〉 통과 (0.05ms, 4.07MB)
테스트 30 〉 통과 (0.03ms, 4.21MB)
테스트 31 〉 통과 (0.01ms, 3.63MB)
테스트 32 〉 통과 (0.01ms, 4.12MB)
테스트 33 〉 통과 (0.01ms, 4.2MB)
테스트 34 〉 통과 (0.01ms, 4.13MB)
테스트 35 〉 통과 (0.01ms, 3.68MB)
테스트 36 〉 통과 (0.01ms, 4.14MB)
테스트 37 〉 통과 (0.01ms, 3.67MB)
테스트 38 〉 통과 (0.01ms, 3.75MB)
테스트 39 〉 통과 (0.01ms, 4.18MB)
테스트 40 〉 통과 (0.01ms, 4.16MB)
테스트 41 〉 통과 (0.05ms, 4.43MB)
테스트 42 〉 통과 (0.07ms, 4.13MB)