문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/140108

문제 설명

문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다. 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다. 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다. s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다. 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다. 문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.

코드

#include<bits/stdc++.h>
using namespace std;

int solution(string s) {
    int answer = 0;
    int cnt = 0;
    auto x = s[0];
    int otherCnt = 0;
    for(int i = 0; i < s.size(); i++){
        //첫번째 글자랑 다음나온 글자가 다르다면?
        if(x == s[i]){
            cnt++;
        } else {
            otherCnt++;
        }
        if(cnt == otherCnt){
            answer++;
            if(i + 1 < s.size()){
                x = s[i + 1];
            }
            cnt = 0;
            otherCnt = 0;
        }
    }
    if(cnt != 0 || otherCnt != 0){
        answer++;
    }

    return answer;
}

문제 접근

먼저, 문자열을 하나씩 읽어가면서 첫 번째 글자를 기억해. 그걸 x라고 정했다.

• 이제 x랑 똑같은 글자가 몇 개 나오는지 세고, x랑 다른 글자도 몇 개 나오는지 세어본다.
• 두 글자의 개수가 딱 같아지면 우리는 여기서 “끝!”이라고 하고, 그 부분까지를 하나의 덩어리로 나누는 거야.
• 그 후, 나머지 글자들에 대해서도 같은 과정을 반복한다.

예시

친구가 줄넘기 시합을 할 때 너랑 친구가 똑같이 줄넘기를 몇 번 했는지 세는 거랑 비슷하다.

• 나랑 친구가 같은 횟수로 줄넘기를 했으면 “끝!” 하고 시합이 종료되면 그러면 한 판이 끝난 것.
• 그 다음에 또 새로운 시합을 시작하는 것.

만약 마지막까지 줄넘기를 하다가 “같은 횟수”가 안 맞으면, 그때까지 한 번 더 나누고 끝내는 로직이다.

코드 설명

이걸 코드로 옮기면 다음과 같아:

1. x라는 첫 번째 글자를 정해.
2. x와 같은 글자 개수(cnt)랑 x와 다른 글자 개수(otherCnt)를 각각 카운팅
3. 두 개수가 같아지면, 한 덩어리로 나누고 그 순간 덩어리 개수(answer)를 하나 늘린다.
4. 새로운 덩어리에서 또 첫 글자 x를 정하고, 다시 똑같이
5. 마지막에 남은 글자가 있으면 그것도 하나의 덩어리로 추가

그래서 최종적으로 몇 개의 덩어리로 나눴는지를 구한다.

문제 해결을 쉽게 접근해보면

1. 첫 글자를 기준으로, 그 글자가 몇 번 나오는지(cnt)랑, 그 글자랑 다른 글자가 몇 번 나오는지(otherCnt)를 카운트 한다.
2. 두 개수가 같아지면 그 순간까지 읽은 부분을 하나의 구간이라고 생각하고, 이 구간을 처리했으니까 이제 다시 남은 문자열로 같은 작업을 반복한다.
3. 계속해서 이 과정을 반복하면서 문자열을 나눈 횟수를 센다.

Reference

나의 뇌