<프로그래머스 C++> 문자열 나누기 풀이

문제 설명

문자열 s가 주어질 때, 다음 규칙으로 문자열을 분해하고 분해한 개수를 반환하는 문제이다.

• 첫 글자를 x로 정한다.
• x와 같은 글자의 수와 다른 글자의 수가 같아지면 문자열을 분리한다.
• 남은 문자열에 대해서 반복한다.
• 끝까지 읽었는데 횟수가 다르면 그대로 분리하고 종료.

---

문제 해석

포인트는 두 가지이다.

 

1. 분해 기준 매 분해마다 첫 글자가 x로 새로 정해진다. "banana"에서 첫 분해는 b가 x가 되고, 다음 분해는 n이 x가 되는 방식이다.

 

2. 끝까지 못 맞추는 경우는 두 횟수가 끝내 같아지지 않으면 남은 문자열 전체를 하나로 분리하고 종료한다. 이 경우도 answer에 +1 해야한다.

---

문제풀이

#include <string>
#include <vector>
using namespace std;

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

    while(i < s.size()) {
        char x = s[i];
        int count1 = 0, count2 = 0;

        while(i < s.size()) {
            if(s[i] == x) ++count1;
            else ++count2;
            ++i;

            if(count1 == count2) {
                ++answer;
                break;
            }
        }

        if(count1 != count2) ++answer;
    }
    return answer;
}

---

핵심 포인트

바깥쪽 while문

분해 반복을 한 번 돌 때마다 문자열을 하나씩 분해한다. i가 끝에 도달하면 종료된다.

 

안쪽 while문

한 덩어리씩 탐색해서 x와 같으면 count1을, 다르면 count2를 증가시켜 매 글자마다 두 카운트가 같은지 체크한다.

같아지면 break하고 answer를 올린 후 다음 문자열을 탐색한다.

 

---

트러블 슈팅

처음에 이중 for문 조작 방식으로 접근했다.

그래서 코드의 결과가 예상하던 바와 다르게 나왔다.

for(int i = 0; i < s.size(); ++i)
{
    char word = s[i];
    for(int j = i+1; j < s.size(); ++j)
    {
        // ...
        if(count1 == count2)
        {
            ++answer;
            i += j;  // 다음 시작점으로 이동
            break;
        }
    }
}

 

i += j로 다음 시작점을 이동시키는 방식이었다.

 

예시인 "banana"를 기준으로 추적하면

i=0, word='b'
  j=1, 'a' != 'b' → count1==count2 → answer=1
  i += j-1 → i += 0 → i=0
바깥 ++i → i=1

i=1, word='a'
  j=4에서 count1==count2 → answer=2
  i += j-1 → i += 3 → i=4
바깥 ++i → i=5

i=5, word='a'
  j=6 → 안쪽 루프 안 돎 → 마지막 "na" 분리 실패

마지막 문자열인 "na"를 체크하지 못해서 answer = 2가 나와 오답이 되었다.

 

해결방법

정답 코드와 같이, 이중 for문에서 i를 하나로 지정하고 바깥쪽과 안쪽 while문이 공유하는 구조로 변경했다.

안쪽 while에서 증가된 i 값은 안쪽 루프가 끝나고 바로 다음 가리켜야 할 문자열의 시작 위치로 이동하기 때문에 이 방식을 사용해도 옳은 방향으로 진행되었다.

 

인덱스도 두 가지를 사용하면서 꼬일 걱정이 없었다.