177일 (CodeTestcaseTestcaseTest Result525. Contiguous Array) Map, 매우 어려움

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

 

 

Example 1:

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

 

 

 

Example 2:

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.

 

 

 

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.

 

 

- 접근방법

 

nums = [0,0,1,0,0,1] 일때 혹은 nums = [1,0,0,1,0,0] 일때는 쉽게 원하는 서브배열의 길이를 구하기 쉽다.

하지만 nums = [0,0,1,0,0,1,0,0] 일때는? 어떻게 원하는 서브배열의 길이를 구할 수 있을까?

 

1. Map을 이용한다.

 

현재 위치가 0일 경우 cnt는 1이 감소하고, 현재 위치가 1일 경우 cnt는 증가한다.

nums = [0,0,0,1,0,1] 일때 -1 -2 -3 -2 -3 -4를 키로 인덱스 0~5를 밸류 값으로 맵에 저장한다.

cnt에 현재 nums[i]가 0일 경우 -1 1일 경우 +1을 한다.

 

 

2. 만약 기존에 저장된 키(cnt)와 현재 cnt가 같을경우?

nums = [0,0,0,1,0,1] 일때 키는 (-1, -2, -3, -2, -3, -4)이 된다. (-3인 경우는 생략하고 -2만을 예시로 든다.)

 

nums의 인덱스 0번과 1번을 제외한 2번 3번이 0과 1의 합이 같은 부분배열이 된다. [0,0,0,1]

기존의 -2는 지금까지 0이 2번 존재하였다는 의미만을 갖고, 이 값은 -2보다 더 작아질수도 더 커질수도 있다

 

하지만 언젠가 -2로 돌아온다면 기존의 -2 이후부터 현재 -2까지의 거리가 우리가 원하는 부분배열의 길이가 된다.

→ -2에서 -5로 변하고 -2로 돌아왔다면 0이 3개 추가되고 1이 3개 추가된 것뿐 기준인 -2까지 돌아온 것이다.

단지 -2의 의미는 이 이전에 0이 2번 나타났다는 의미일 뿐이다.

ex) 0,0, 0,0,0,1,1,1 → -2에서 -5로 -5에서 다시 -2로 돌아왔다는 뜻. 총 6의 길이가 0과 1의 합이 같은 부분배열의 길이.

 

 

 

- 코드 

class Solution {
    public int findMaxLength(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int maxLength = 0;
        int cnt = 0;

        map.put(0, -1);

        for (int i = 0; i < nums.length; i++) {
            cnt += nums[i] == 1? 1 : -1;

            if (map.containsKey(cnt)) { // 2
                maxLength = Math.max(maxLength, i - map.get(cnt));
            }
            else { // 1
                map.put(cnt, i);
            }
        }

        return maxLength;
    }
}

 

오랜만에 못 풀었다..
그래서 다른 사람의 솔루션을 봤는데도 이해가 잘 되지 않아서 고민을 많이 했다.
Map이 알려주는 정보를 어떻게 해석해야 할지 갈피가 잡히지 않았기 때문이다.

이틀전 문제도 그렇고 오늘 문제도 그렇고 아마 내일 풀어도 또 틀릴 것 같다..

적절한 자료구조를 선택하는 문제들은 쉬운데 알고리즘을 적용하는 문제들은 상당히 난이도 편차가 크다.

 

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