Leetcode[day13] - Contiguous Array

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

Note: The length of the given binary array will not exceed 50,000.

 

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

 

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

 

1. 알고리즘을 해결하기 위해서 생각한 방법 & 어려운 점

 

 - 0과 1로 주어진 array에서 0과 1의 숫자를 카운팅 했을 때, 0과 1의 카운팅 숫자가 같은 가장 긴 배열의 길이를 구하여라가 문제였다.

 - 10000111, 일 때 1과 0이 4개씩이다 보니, 이럴 때 가장 긴 배열이 성립된다.

 - 그래서 해당 문제를 해결하기 위해서 왼쪽에서부터 숫자를 카운팅해서 같을 때, 오른쪽에서부터 숫자를 카운팅해서 같을 때를 검사해서, Math.max(왼쪽,오른쪽) 으로 길이를 구하는 알고리즘을 생각했다.

 - 하지만, 00100100과 같을 때, 가운데 '1001'이 가장 긴 배열이 되는데, 위의 알고리즘은 이 문제를 해결할 수 없다.

 - 그러면 00100100의 배열일 때, 앞에서부터 하나씩 카운팅을 하는 것은 어떨까를 생각했다.

 00100100, 0100100, 100100, 00100, 0100, 100 이런식으로 하면 어떨까 했는데, 그러기엔 시간복잡도가 엉망이었다.

 -그래서 결국 못 풀었다.

 

2. 내가 작성한 알고리즘

 

//포기~~

 

3. 흠... 모르겠다. 모르겠다리~~

 

그래서, 내가 최근 구독한 유튜버의 글을 보게 되었다.

https://www.youtube.com/watch?v=63ogoiDrd4g

 

4. 해당 영상을 보면서, 배운 점

 

1. 1과 0이 들어올 때, 길이를 구하기 위해서는 1은 1, 0은 -1로 치환해줘야 한다.

 

nums[i] * 2 - 1; //nums[i]가 0이면 -1, 1이면 1

 

2. nums[i] * 2 - 1을 각 배열의 길이만큼 치환해준다.

3. sum += nums[i] * 2 -1 을 통해서 배열의 길이만큼 치환해준다.

4. 그럴 때, sum이 제일 먼저 나타난 index를 기억해뒀다가 추후에 해당 sum과 같은 수가 나오면 인덱스끼리 빼준다.

5. 그 중, 가장 큰 값이 가장 긴 값이 된다.

class Solution {
    public int findMaxLength(int[] nums) {
        //0,1,0,1,0,1,0,0
                
        return getMaxLength(nums);
    }
    
    private int getMaxLength(int[] nums){
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        int maxLength = 0;
        map.put(0,-1);
        for(int i=0; i < nums.length; i++){
            int oneAndMinusOne = nums[i] * 2 - 1;
            sum += oneAndMinusOne;
            if(map.containsKey(sum)){
                int startIndex = map.get(sum);
                maxLength = Math.max(maxLength, i - startIndex);
            }else{
                map.put(sum, i);
            }
        }
        
        return maxLength;
    }
}

 

5. 다른 사람이 작성한 알고리즘을 보고 배운점

 

 - 또한, 해당 문제를 풀기위해서 map을 사용했는데, map의 성능을 개선하기 위해서 array로 변경해야한다.

 - 배열을 nums의 사이즈보다 2배 크게 한 후, 0번 째 인덱스를 nums.length부터 시작하게 하면, 가운데부터 값을 넣을 수 있는 map이 만들어진다.

 

class Solution {
    public int findMaxLength(int[] nums) {
        //0,1,0,1,0,1,0,0
                
        return getMaxLength(nums);
    }
    
    private int getMaxLength(int[] nums){
        int[] map = new int[nums.length * 2 + 1];
        int INITIALIZE = nums.length;
        int sum = 0;
        int maxLength = 0;
        int EMPTY = nums.length *2 + 1;
        for(int i=0; i < map.length; i++){
            map[i] = EMPTY;
        }
        map[INITIALIZE] = -1;
        for(int i=0; i < nums.length; i++){
            int oneAndMinusOne = nums[i] * 2 - 1;
            sum += oneAndMinusOne;
            if(map[INITIALIZE + sum] != EMPTY){
                int startIndex = map[INITIALIZE+sum];
                maxLength = Math.max(maxLength, i - startIndex);
            }else{
                map[INITIALIZE+sum] = i;
            }
        }
        
        return maxLength;
    }
}

 

6. 반성할 점

 

 - 0과 1을 -1과 1로 할 수 있도록 한 알고리즘과 같이, 주어진 값을 통해, 문제를 풀 수 있도록 값을 변경하는 것을 항상 생각해야한다.

 - 레퍼런스 타입보다는 원시 타입이 속도가 빠르다.

 - 누적된 값은 가장 긴 길이를 구하기 위한 가장 중요한 요소이다.

 

7. 짝짝짝 결과

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3298/

Explore - LeetCode