프로그래머스 [연습문제 / 문자열 나누기](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 문자열 나누기

---

문제 링크: 문제 보기

문제 설명:

하나의 문자열을 왼쪽부터 읽으면서, 처음 나온 문자와 다른 문자의 수가 같아질 때 분리하여 나눌 수 있는 문자열 개수를 구하는 문제입니다. 이 과정을 반복하여 전체 문자열을 다 나눌 수 있습니다.

---

문제 해결 코드

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    for (int i = 0; i < s.size(); i++) {
        if (i == s.size() - 1) { // 마지막 문자까지 왔다면 바로 하나로 분리
            answer++;
            break;
        }

        int cnt1 = 1; // 기준 문자 등장 횟수
        int cnt2 = 0; // 다른 문자 등장 횟수

        for (int j = i + 1; j < s.size(); j++) {
            if (s[i] == s[j]) cnt1++;
            else cnt2++;

            if (cnt1 == cnt2) {
                i = j; // i를 j로 옮겨서 다음 구간 시작
                answer++;
                break;
            }

            if (j == s.size() - 1) {
                i = j; // 끝까지 읽었는데 균형 못 맞춰도 하나로 처리
                answer++;
            }
        }
    }

    return answer;
}

---

코드 설명

• 핵심 알고리즘: 왼쪽에서부터 순차적으로 탐색하며 같은 문자 수와 다른 문자 수가 같아지는 순간 분리하는 방식으로 해결합니다.
• 구현 세부사항:
• cnt1은 현재 구간의 기준 문자의 등장 횟수, cnt2는 나머지 문자의 등장 횟수입니다.
• 두 값이 같아지면 하나의 구간으로 분리 가능하므로 answer를 증가시키고 다음 인덱스로 이동합니다.
• 문자열의 마지막까지 도달해도 분리 조건이 안 되면, 그 구간 전체를 하나로 처리합니다.
• 시간 복잡도 분석:
• 최악의 경우 O(n²)이지만, 조건이 맞는 순간 빠르게 분리되기 때문에 평균적으로 O(n)에 가깝습니다.

---

결과

이 코드는 주어진 문자열을 조건에 맞게 분리하여 가능한 최대 구간 수를 반환합니다. 문제 조건을 그대로 구현하여 직관적이며 효율적인 방식으로 풀이하였습니다.

다른 접근으로는 문자열을 한 번만 순회하며 분리 지점을 찾는 방식이 있지만, 본 방식이 가장 직관적이며 조건에 잘 맞습니다.