[Leetcode] 696. Count Binary Substrings

✏️리트코드 스터디 4일차.

696. Count Binary Substrings

그동안 스터디를 진행하면서 이렇게까지 막막하고 감을 잡기 어려웠던 문제는 처음이라 구글링의 도움을 약간 받았다. 사실 한글로 된 글이 거의 없어서 대충 intuition을 보면서 감만 잡고있는데 어느 순간 딱 feel이와서 코드를 짜봤더니 Accept됐다,,,😂

(사실 스터디 자료를 블로그에 올려야겠다고 생각하게 된 계기이기도 하다. 구글링하시는 분들께 조금의 도움이라도 된다면,,,😇)

문제

해석:
이진 문자열 s가 주어집니다.
s안에서 0과 1의 수가 같고 비어있지 않은 하위 문자열의 수를 반환합니다.
이 하위 문자열의 모든 0과 모든 1은 연속적으로 그룹화됩니다.

여러 번 발생하는 하위 문자열은 각각 개수를 셉니다.

---

입력:

• 매개변수 s: 0과 1로 이루어진 문자열. 1 <= s.length <= 100,000

---

출력:

• 하위 문자열 수

처음에 오늘 배운 two-pointers로 접근을 해봤으나 결국 삽질이었다.
일단 20분이 지났을 때 썼던 건, 거의 이게 다였다.(뭔가 0과 1이 바뀌는 시점에 뭔갈 해야될 것 같긴하지만, 뭘 어떻게 해야할지는 모르겠는,,,)

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        answer=0
        count=0
        for i in range(len(s)-1):
            if s[i]!=s[i+1]:
        return answer

그 후로도 한참 셋이서 머리를 싸매고 토론을 했지만 풀이 방향을 잡기도 쉽지 않았다.
부분집합의 길이는 무조건 짝수라는건 나왔지만, 그마저도 가변적이기 때문에 투포인터스를 어떤식으로 해야할지 막막했다.

0과 1이 각각 뭉쳐있어야 된다는 조건때문에 골치아팠는데, 사실 실마리는 거기에 있었다.

결국 0과 1의 개수가 같아야하고, 0과 1이 각각 붙어있어야 한다면,
모든 부분집합의 모양새는 0과 1이 각각 반씩 구성된 형태일 것이다.

그렇다면 0과 1이 반복되는 개수(길이)를 가지고 부분집합 수를 카운팅 할 수 있겠다는 아이디어가 나온다.

예를 들어 0001111은 0 3개, 1 4개이다. 그러면 더 작은 숫자인 3을 선택해 0과 1이 3개씩 들어간 000111의 부분집합을 만들수있고, 이 안에서 만들어지는 부분집합의 개수는 3이다. 가운데를 기준으로 01, 0011, 000111 이렇게 만들어질 수 있기 때문이다. 즉 붙어있는 0 덩어리와 1 덩어리 중에서 더 짧은 덩어리의 길이가 곧 그 부분의 부분집합의 개수가 되는 것이다.

이러한 아이디어를 바탕으로 완성한 코드이다.
각 0과 1의 덩어리들의 길이를 nums라는 리스트에 차례로 append시켜주었다.
그 다음 len(nums)-1만큼 for문이 돌면서 원소 두 개 씩 비교하여 더 작은 값을 answer에 더해주었다.

ver.1

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        s=s+' '
        answer=0
        count=0
        nums=[]
        for i in range(len(s)-1):
            count+=1
            if s[i]!=s[i+1]:
                nums.append(count)
                count=0
        for x in range(len(nums)-1):
            answer+=min(nums[x],nums[x+1])

        return answer

위의 코드에서 달라진 것은 0, 1의 개수(덩어리 길이)를 append 시켜주는 시점이다.
위의 코드에서는 문자가 달라지기 전까지 카운트해주다가 달라졌을 때 그 카운트를 append해준다. 따라서, s의 끝에 빈 문자열(' ')을 추가해주지 않으면, 마지막에 if문이 돌지를 않아서 마지막 덩어리의 길이는 리스트에 누락된다.

이를 수정한 방법이 ver.2 이다. 여기서는 먼저 리스트에 1을 append시켜주고 같은 숫자가 반복되는 만큼 카운트를 더해준다. 따라서 누락될 일이 없다.
ver.1 코드 제출 후에 solution을 확인해보니 저 방법이 나와있어 또 하나 배웠다👍

ver.2

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        answer=0
        nums=[1]
        for i in range(len(s)-1):
            if s[i]!=s[i+1]:
                nums.append(1)
            else:
                nums[-1]+=1
        for x in range(len(nums)-1):
            answer+=min(nums[x],nums[x+1])

        return answer

생각은 유연하게! 코드는 단순하게!
코딩 좌우명, 오늘도 머리에 새긴다.