[프로그래머스] 문자열 나누기 - 파이썬

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

문제 설명

문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.

• 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
• 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.
• s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.
• 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.

문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.

---

제한사항

• 1 ≤ s의 길이 ≤ 10,000
• s는 영어 소문자로만 이루어져 있습니다.

---

입출력 예

s	result
"banana"	3
"abracadabra"	6
"aaabbaccccabba"	3

---

입출력 예 설명

입출력 예 #1

s="banana"인 경우 ba - na - na와 같이 분해됩니다.

입출력 예 #2

s="abracadabra"인 경우 ab - ra - ca - da - br - a와 같이 분해됩니다.

입출력 예 #3

s="aaabbaccccabba"인 경우 aaabbacc - ccab - ba와 같이 분해됩니다.

---

문제풀이

문제 이해하기:

• 문자열 s 가 주어진다.
• 문자열의 첫 글자를 읽고, 이를 x 라고 한다.
• x 부터 오른쪽으로 읽어나가면서 x 와 x 가 아닌 다른 글자들이 나온 횟수를 각각 셀건데, 처음으로 같아지는 순간 멈추고 지금까지 읽은 문자열을 분리한다.
• 위의 단계를 반복한다.
  • 이 때 두 횟수가 다른 상태에서 더이상 읽을 글자가 없어도 지금까지 읽은 문자열을 분리하고 종료!
• 예시
  • s = ‘aaabbaccccabba’
  • x 가 나온 횟수: x_count, 나머지 글자가 나온 횟수: other_count
  • 이는 aaabbacc, ccab, ba 로 나눌 수 있는데
    • aaabbacc : 여기서 x 는 a. a 가 3번 나오고 다음 b가 2번 나왔으니 여기까지 x_count = 3, other_count = 2 이다. 그래서 다음 a 를 읽고 뒤에 c 두개를 읽으면 x_count = 4, other_count = 4 로 둘이 같아졌기 때문에 여기까지의 문자열을 분리.
    • ccab : c 두 번 나오고 a 1번 b 1번으로 x_count = other_count 이므로 여기까지의 문자열 분리.
    • ba : b 1번 = a 1번 → 분리

최종코드

def solution(s):
    answer = 0
    i = 0  # 인덱스 시작 위치

    while i < len(s):
        x = s[i]
        x_count = 0
        other_count = 0

        for j in range(i, len(s)):
            if s[j] == x:  # x 와 같은 문자면 x_count 올리고
                x_count += 1
            else:  # 나머지 다른 문자면 other_count 를 올린다.
                other_count += 1

            if x_count == other_count:
                i = j + 1  # 분리된 문자열 다음 인덱스로 이동
                break
        else:
            i = len(s)  # 남은 부분이 더 이상 없을 때

        answer += 1

    return answer