[코딩테스트] 릿코드 696 Count Binary Substrings - 파이썬

문제 출처 - https://leetcode.com/problems/count-binary-substrings/

• 문제 설명
• 결과 값이 될 수 있는 구조 생각하기
• 최종풀이

👌 문제 설명

입력 - 0과 1로 이루어진 문자열(ex 1001011)
조건 - 0과 1의 개수가 똑같으며, 0과 1은 연속적이어야 한다.
(ex 10(o), 1100(o), 0011(o), 0110(x) 0이 연속적이지 않음.)
출력 - 조건을 만족하는 모든 서브 스트링의 개수

👌 결과 값이 될 수 있는 구조 생각하기

문제를 처음 보고 거의 10분간은 해답을 전혀 생각하지 못했던 것 같다.
우선 영어로 되어있는 문제 설명을 제대로 해석하지 못한 것도 있지만 그냥 결과값을 빠트림없이 모두 찾는 방법을 몰랐었다.

그러다 올바른 출력 값의 예시와 틀린 출력 값의 예시를 보고 풀이법이 생각났다. 정확히는 결과 값이 되는 값들의 규칙, 즉 구조를 파악한 것이다.
결과 값은 "0n개 + 1n개" 혹은 "1n개 + 0n개" 구조일 수 밖에 없다.

👌 최종 풀이

1. 입력받은 문자열에서 "기준 숫자(pivots)"가 바뀔 때, 연속 됐던 개수만 저장해둔다. (ex "110010" -> [2,2,1,1] 형식)

2. 개수를 세둔 리스트에서 i번째 항목과 i+1번째 항목을 비교하여 더 작은 값을 더해 최종 개수를 구한다.

def getSubstringCount(s):
    continous_cnt = []
    count = 0
    result = 0
    pivot = s[0]
    for i in s:
        if i != pivot:
            continous_cnt.append(count)
            count = 1
            pivot = i
        else:
            count += 1

    if count > 1:
        continous_cnt.append(count)
    else:
        continous_cnt.append(1)

    for i in range(len(continous_cnt) - 1):
        result += min(continous_cnt[i], continous_cnt[i + 1])

    return result