[2024] day 77. Leetcode 239. 525. Contiguous Array

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 16일 (토)
Leetcode daily problem

525. Contiguous Array

https://leetcode.com/problems/contiguous-array/description/?envType=daily-question&envId=2024-03-16

Problem

0과 1로 이루어진 이진 배열이 주어질 때, 이진 배열에서 0과 1의 개수가 같은 연속된 부분 배열의 최대 길이를 찾아 반환한다.

Solution

hash map

해당 문제는 해당 배열을 순차적으로 탐색하면서 요소들의 누적합을 key로하고, 해당 인덱스를 value로 하는 해시맵을 사용하는 것이다.
배열을 순차적으로 탐색하면서 0을 만나면 카운트를 1 감소시키고, 1을 만나면 카운트를 1 증가시킨다.

그래서 +1, -1을 해가면서 누적합이 0이 되는 지점이 0과 1의 개수가 같은 지점이라고 이해할 수 있다. 이 때 이 부분 배열의 길이를 계산하고, 그 길이가 지금까지 찾은 최대 길이보다 크면 최대 길이를 업데이트 하는 방식으로 최대 길이를 찾아나간다.

배열을 탐색해나가면서 각 고유한 카운트 값을 해시맵에 저장하고, 동일한 카운트가 다시 발생하면, 해당 카운트가 발생한 이전 인덱스와 현재 인덱스 사이의 부분 배열이 0과 1의 개수가 같다는 것을 의미한다. (0과 1의 개수가 동일한 서브어레이를 찾기 위해서는 누적 카운트를 사용하는데, 이전에 동일한 누적 카운트가 나타났던 인덱스와 현재 인덱스의 차이가 해당 서브어레이의 길이를 나타낸다. 만약 동일한 누적 카운트가 두 번째로 나타나면, 그것은 현재 인덱스와 이전에 나타난 인덱스 사이에 0과 1의 개수가 동일한 서브어레이가 있음을 의미한다)

배열이 [0,1,0,1] 이 주어졌다고 할 때

0번째 인덱스에서의 누적합은 -1이다. 해당 누적합에 대한 값이 해쉬에 담겨져 있지 않으므로, 해당 누적값 -1에 대한 인덱스 값을 해시에 업데이트 한다.
1번째 인덱스에서의 누적합은 0이다. 이 때 0과 1의 개수가 같은 순간이다.
배열을 순환하면서 처음에 0과 1의 개수가 같은 순간의 길이를 측정하기 위해 제일 처음 해시에 0을 key로 하는 value값을 -1로 초기화 해놓아 현재까지의 0과 1의 개수가 같은 subarray의 길이를 2가 나오도록 한다.

2번째 인덱스에서의 누적합은 -1이고, 이전에 0번 인덱스에서 해당 누적값이 나왔기 때문에 -1에 해당하는 값을 인덱스 2로 업데이트 한다.
3번째 인덱스에서 누적합은 0이되고, 이 때 0과 1의 개수가 같은 순간이므로
현재의 인덱스의 길이와 해시에 0을 key로 하는 value와의 차이를 통해 최종 길이인 4를 반환한다.

이러한 식으로 문제를 해결하면된다.
쉬워보였는데, 누적합이 없을 때의 값들을 왜 누적해 가야하는지에 대해 의문이 생겨서 조금 오래걸렸다.
누적합이 이미 해시에 있으면, 이전에 등장한 cnt의 인덱스와 현재 인덱스 사이의 부분 배열이 0과 1의 개수가 동일하다는 의미이기 때문에 따라서 최대 길이 서브어레이를 찾아야 하므로 최대 길이를 업데이트하는 것이다.

Code

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        cnt = 0
        maxLen = 0
        sumIdx = {0:-1}

        for i in range(len(nums)):
            if nums[i] == 0:
                cnt -=1
            else:
                cnt +=1
            
            if cnt in sumIdx:
                maxLen = max(maxLen, i-sumIdx[cnt])
            else:
                sumIdx[cnt] = i

        return maxLen

Complexicity

시간 복잡도

주어진 배열을 한 번만 탐색하면서 각 인덱스마다 누적 카운트를 계산하고 인덱스를 딕셔너리에 저장한다.누적 카운트나 추가 연산은 상수 시간 O(1)이지만 배열을 탐색하는데 O(n)이 소요되므로 총 시간복잡도는 O(n)이 된다.

공간 복잡도

주어진 배열의 각 누적 카운트와 해당 인덱스를 저장하기 위해 딕셔너리를 사용한다. 딕셔너리의 키와 값의 개수는 배열의 길이에 비례하므로 공간 복잡도는 O(n)이다.