문자열을 왼쪽에서 오른쪽으로 읽어나가면서,x와 x가 아닌 다른 글자들이 나온 횟수를 각각 카운트.처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리
s에서분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복. 남은 부분이 없다면 종료
만약두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료
분해한 문자열의 개수를 return
제한사항
1 ≤ s의 길이 ≤ 10,000
s는 영어 소문자로만 이루어져 있음
"""
입출력 예시)
s = "banana" -> 3
s = "abracadabra" -> 6
s = "aaabbaccccabba" -> 3
"""
# s "banana" -> 3
# ba - na - na
# s "abracadabra" -> 6
# ab - ra - ca - da - br - a
# s "aaabbaccccabba" -> 3
# aaabbacc - ccab - ba
## 의사코드 ##
# 결과를 담을 리스트 생성 ['', 0, 0] -> 문자열x, x가 나온 횟수, x가 아닌 문자가 나온 횟수
# for i in s:
# if 리스트[0] == '': (문자열이 비어있으면)
# 리스트[0] = i (s의 첫 번째 문자가 x가 됨)
# 리스트[1] += 1 (x가 나온 횟수 + 1)
# else: (문자열이 비어있지 않은 경우 -> x가 지정되어 있을 때)
# if 리스트[0] == i: (현재 문자가 x이면)
# 리스트[1] += 1 (x가 나온 횟수 + 1)
# else: (현재 문자가 x가 아니면)
# 리스트[2] += 1 (x가 아닌 문자가 나온 횟수 +1)
# if 리스트[1] == 리스트[2]: (x가 나온 횟수와 x가 아닌 문자가 나온 횟수가 같으면)
# answer += 1 (분해한 문자열의 개수 + 1)
# 리스트 = ['', 0, 0] (리스트 초기화)
# if 리스트 != ['', 0, 0]: (리스트가 초기화된 리스트가 아니면 => 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없는 경우)
# answer += 1 (지금까지 읽은 문자열을 분리)
통과한 코드
def solution(s):
answer = 0
temp = ["", 0, 0] # 문자열x, x가 나온 횟수, x가 아닌 문자가 나온 횟수
for i in s:
# 문자열이 비어있는 경우 -> x가 아직 지정되지 않았을 때
if temp[0] == "":
temp[0] = i # x는 현재 문자 (s의 첫 번째 문자)
temp[1] += 1 # x가 나온 횟수 + 1
# 문자열이 비어있지 않은 경우 -> x가 지정되어 있을 때
else:
# 현재 문자가 x이면
if temp[0] == i:
temp[1] += 1 # x가 나온 횟수 + 1
# 현재 문자가 x가 아니면
else:
temp[2] += 1 # x가 아닌 문자가 나온 횟수 +1
# x가 나온 횟수와 x가 아닌 문자가 나온 횟수가 같으면
if temp[1] == temp[2]:
answer += 1 # 분해한 문자열의 개수 + 1
temp = ["", 0, 0] # 리스트 초기화
# 리스트가 초기화된 리스트가 아니면 -> 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없는 경우
if temp != ["", 0, 0]:
answer += 1 # 지금까지 읽은 문자열을 분리, 분해한 문자열의 개수 + 1
return answer
처음에는 문자열 x를 구하고, s의 i번째 문자와 i+1번째 문자를 비교해서 나온 횟수를 카운트 한 다음,
분해 조건을 만족하면 분해한 문자열을 따로 리스트에 저장해서 answer = len(리스트)로 하려고 했다.
근데 그냥 리스트 하나로 한번에 바로 문자열 x와 x가 나온 횟수, x가 아닌 문자가 나온 횟수를 저장하면 훨씬 쉽게 풀 수 있었다.
과정 확인
s = "aaabbaccccabba"
solution(s)
"""
temp[0]: a # 문자열 x
temp: ['a', 1, 0]
___________________________
temp[0]: a
i: a
temp: ['a', 2, 0]
temp[0]: a
i: a
temp: ['a', 3, 0]
temp[0]: a
i: b
temp: ['a', 3, 1]
temp[0]: a
i: b
temp: ['a', 3, 2]
temp[0]: a
i: a
temp: ['a', 4, 2]
temp[0]: a
i: c
temp: ['a', 4, 3]
temp[0]: a
i: c
temp: ['a', 4, 4]
temp: ['', 0, 0] # 리스트 초기화
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
temp[0]: c # 문자열 x
temp: ['c', 1, 0]
___________________________
temp[0]: c
i: c
temp: ['c', 2, 0]
temp[0]: c
i: a
temp: ['c', 2, 1]
temp[0]: c
i: b
temp: ['c', 2, 2]
temp: ['', 0, 0] # 리스트 초기화
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
temp[0]: b # 문자열 x
temp: ['b', 1, 0]
___________________________
temp[0]: b
i: a
temp: ['b', 1, 1]
temp: ['', 0, 0] # 리스트 초기화
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
3
"""