[프로그래머스/Day 19] 문자열 나누기 - Map에서 단순 카운팅으로 최적화하기

오늘은 프로그래머스 '문자열 나누기' 문제를 풀면서 겪었던 시행착오와, 이를 통해 도출한 최적화된 풀이 과정을 정리해 보았습니다.

1. 문제 개요

이 문제는 문자열 s를 입력받아 규칙에 따라 여러 문자열로 분해하고, 분해된 문자열의 개수를 구하는 문제입니다. 핵심 규칙은 다음과 같습니다.

1. 문자열을 앞에서부터 읽으며, 첫 글자를 $x$라고 합니다.
2. 이제부터 읽는 글자들이 $x$인 횟수와 $x$가 아닌 다른 글자인 횟수를 셉니다.
3. 두 횟수가 처음으로 같아지는 순간, 지금까지 읽은 문자열을 분리합니다.
4. 분리 후 남은 부분에서 다시 1번부터 반복합니다.
5. 중요: 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 남은 문자열을 분리하고 종료합니다.

---

2. 알고리즘 선택 과정

초기 접근: std::map과 인덱스 점프

처음에는 map을 사용하여 등장하는 문자의 개수를 세고, 조건이 충족되면 인덱스(i)를 분해된 길이만큼 강제로 건너뛰는 방식을 생각했습니다.

• 초기 로직:
  • cMap에 문자를 카운팅.
  • s[i]와 s[i+1]을 비교하여 로직 처리.
  • 조건 만족 시 i += ... 연산으로 인덱스 조작.

문제점 발견

구현을 하다 보니 코드가 복잡해지고, 예외 처리가 까다로워졌습니다.

1. 불필요한 정보: 문제에서는 "$x$인가, 아닌가"만 중요한데, map은 $x$가 아닌 문자들(b, c, d...)을 모두 구분해서 저장하므로 불필요한 메모리와 연산을 사용합니다.
2. 인덱스 관리의 어려움: for문의 증감식을 비워두고 내부에서 인덱스를 직접 조작하다 보니, 루프 흐름을 제어하기 어렵고 실수할 여지가 많았습니다.
3. 논리 오류: "처음 나온 문자의 개수"와 "그 외 문자의 개수"를 비교해야 하는데, 단순히 인접한 두 문자의 개수만 비교하는 오류를 범했습니다.

최적화: 단순 카운터 변수 (int)

생각을 전환하여 자료구조를 최대한 단순화했습니다. 굳이 어떤 문자인지 기록할 필요 없이, "주인공($x$)의 개수"와 "나머지(Other)의 개수"만 비교하면 된다는 점을 깨달았습니다.

• 수정된 로직:
  • map 제거 → x_count, other_count 두 개의 int 변수 사용.
  • 인덱스 점프 제거 → 0부터 끝까지 한 칸씩 순차 탐색.
  • 조건 만족 시(x_count == other_count) 정답을 증가시키고 카운터 초기화.

---

3. 구현 코드 (C++)

최적화된 로직을 적용한 최종 코드입니다.

#include <string>

using namespace std;

int solution(string s) {
    int answer = 0;

    // 현재 세고 있는 부분 문자열의 첫 글자
    char x = s[0]; 
    int x_count = 0;     // x의 개수
    int other_count = 0; // x가 아닌 글자의 개수

    for (int i = 0; i < s.length(); ++i) {
        // 1. 새로운 분해가 시작되는 시점이라면 기준 문자(x) 갱신
        if (x_count == 0 && other_count == 0) {
            x = s[i];
        }

        // 2. 개수 세기
        if (s[i] == x) {
            ++x_count;
        } else {
            ++other_count;
        }

        // 3. 두 횟수가 같아지면 분해
        if (x_count == other_count) {
            ++answer;
            // 카운터 초기화 (다음 루프에서 새로운 x를 잡게 됨)
            x_count = 0;
            other_count = 0;
        }
    }

    // 4. 카운트가 남아있는 경우 문자열 분리
    if (x_count != other_count) {
        ++answer;
    }

    return answer;
}

---

4. 회고

이번 문제를 통해 "문제의 본질에 맞는 자료구조 선택"의 중요성을 다시 한번 느꼈습니다.

• 추상화의 힘: 문제에서 요구하는 것은 구체적인 문자의 종류가 아니라, 오직 대조군($x$ vs Not $x$)의 비율이었습니다. 이를 파악하고 map을 버린 순간 코드가 훨씬 간결해졌습니다.
• Greedy 접근: 인덱스를 복잡하게 계산하기보다, 앞에서부터 조건을 만족하는 즉시 잘라내고 상태를 초기화하는 방식이 훨씬 직관적이고 오류가 적다는 것을 확인했습니다.
• 예외 처리: "더 이상 읽을 글자가 없을 때" 남은 문자열을 처리하는 조건을 놓치지 않는 것이 정답을 맞히는 결정적인 열쇠였습니다.

앞으로도 복잡하게 풀고 있다는 느낌이 들 때는, 불필요한 정보를 관리하고 있는 건 아닌지 점검해 봐야겠습니다.