525. Contiguous Array

[zeikar]

Problem link

https://leetcode.com/problems/contiguous-array

Problem Summary

배열에서 0과 1의 숫자가 같이 나오는 부분 배열을 구하는 문제

Solution

지금까지 0과 1이 나온 카운트를 트래킹 해주면서 같은 카운트가 나왔다면 그때 0과 1이 같은 개수로 나온 배열이 된다.

말로 하니 어려운데 에디토리얼 그림을 보면 이해하기 쉽다.

[0 0 1 0 0 0 1 1] 에 대한 카운트에 따른 그림이고 A, B, C 지점을 찍었을 때 해당 구간은 0과 1이 같은 개수로 나온 부분 배열이 된다.

A-B: 10
B-C: 0011
A-C: 100011

이런 식으로 배열에 대해 카운트의 인덱스를 저장하면서 죽 돌아주면 된다.

Source Code

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        indices = {}

        res = 0
        cnt = 0
        indices[0] = -1

        for i, num in enumerate(nums):
            if num == 1:
                cnt += 1
            else:
                cnt -= 1
            
            if cnt in indices:
                res = max(res, i - indices[cnt])
            else:
                indices[cnt] = i
        return res