[LeetCode] 525. Contiguous Array

문제

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

이진배열이 주어질 때, 연속적으로 0과 1의 개수가 똑같은 배열의 최대 길이를 반환하면 됩니다.

예시

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

 

풀이

배열을 순차적으로 순회하며 0이면 -1, 1이면 +1을 해주는 count 변수를 만들어줍니다.

 

 

count가 같다는건 두 인덱스 사이의 0과 1의 개수가 일치한다는걸 의미합니다.

박스로 표시된 배열의 0과 1의 개수를 한번 세어보세요.

 

 

 

 

 

 

 

 

 

 

 

주황색 네모와 빨간색 네모 중 최대 길이의 배열은 빨간색 네모입니다

빨간색 네모 배열의 길이를 구하려면, 마지막 인덱스인 4,  첫번째 인덱스인 0을 뺀 4 - 0 = 4 가 됩니다.

 

각 요소의 count에 값을 저장시켜야 겠죠?

이 때, 해시맵을 사용하면됩니다. key값에는 count, value에는 인덱스를 저장시킵니다.

이 때 저장시키면서 key가 중복되는 경우 0과 1의 개수가 일치한다는 거니까 두 배열 사이의 길이를 구해서 최대길이인지 계산도 하면 됩니다.

dec[1] = 0
dec[0] = 1
dec[1] = 2
dec[2] = 3
dec[1] = 4

 

하지만 여기서 주의할 점이 있는데, 배열의 요소가 2개인 경우 문제가 생기게 됩니다.

아래 그림을 보시면, 0과 1의 개수가 똑같지만 count의 값이 다릅니다.

이 경우 위 방법을 그대로 진행하면 문제가 생기게 되겠죠?

 

이 문제를 해결하려면 맨 앞에 가상의 값을 임의로 추가하면 해결할 수 있습니다.

 

코드

class Solution(object):
    def findMaxLength(self, nums):
        dic = {}
        count = answer = 0
        dic[0] = -1
        for i in range(len(nums)):
            count += 1 if(nums[i]) else -1
            if(count in dic):
                answer = max(answer, i - dic[count])
            else:
                dic[count] = i
        return answer

 

 

복잡도

• 시간 복잡도: O(n) 
• 공간 복잡도: O(n)