[leetcode] contiguous array

문제 설명

• 문제 링크
• 0과 1로 구성된 리스트 nums가 주어질 때, 0의 개수와 1의 개수가 동일한 subarray의 최대 길이를 구해야 한다. 만약 nums = [0, 0, 1, 1, 1, 0, 1, 1] 이면, 최대 길이는 6이다.
• 제약 조건: 1 <= nums.length <= 10^5

풀이

1. 브루트포스

풀기 전

• 아이디어가 딱히 떠오르지 않아서 일단 모든 상황을 고려할 수 있을지 생각했다. nums.length를 k라고 하고 모든 subarray를 고려한다고 했을 때, 모든 subarray 개수는 k(subarray 길이가 1인 경우) + k-1(subarray 길이가 2인 경우) + k-2(subarray 길이가 3인 경우) + ... + 1 = k(k+1)/2이다. k의 최대값이 10^5이니까 최대 50억 정도의 값이 나온다. 그런데 subarray가 홀수인 경우는 신경 안 써도 되니까 절반 정도인 25억으로 추정할 수 있다. 보통 1억을 1초로 잡는데 25초면 너무 오래 걸렸다. 그런데 다른 방법이 생각이 안 나서 일단 구현해봤다.

코드

class Solution {
public:
	// 탐색하기 시작할 subarray 크기를 정하는 함수이다.
    // 0이나 1이 하나밖에 없는데 subarray 크기를 크게 잡아봤자 소용이 없으므로,
    // 0과 1의 개수 중 작은 값의 2를 곱한 값을 반환한다.
    int getWindowSize(vector<int> nums) {
        int zeroNum = 0;
        int oneNum = 0;
        for (auto& num : nums) {
            if (num == 0)
                zeroNum++;
            else
                oneNum++;
        }
        return min(zeroNum, oneNum) * 2;
    }

    int findMaxLength(vector<int>& nums) {
    	// 탐색을 시작할 subarray 크기를 받아온다.
        // 해당 값부터 시작하여 2씩 크기를 줄여나간다.
        int windowSize = getWindowSize(nums);

		// 현재 subarray의 값을 모두 더한다.
        int initSum = 0;
        for (int i=0; i<windowSize; i++)
            initSum += nums[i];

		// subarray 크기를 2씩 줄이면서 탐색 시작한다.
        for (int size=windowSize; size >= 2; size -= 2) {
        	// 종료 조건 체크
            // nums는 0과 1로만 이루어져 있으므로, 합의 2배가 subarray 크기와 같으면 종료한다.
            if (initSum * 2 == size)
                return size;
                
            int sum = initSum;
            // subarray를 옆으로 옮기면서 종료 조건을 체크한다.
            for (int i=1; i+size <= nums.size(); i++) {
                sum -= nums[i-1];  // subarray에서 벗어난 값을 빼준다.
                sum += nums[i+size-1];  // subarray에 추가된 값을 더해준다.

				// 종료 조건 체크
                if (sum * 2 == size)
                    return size;
            }

			// subarray 크기를 2 줄일거기 때문에, 맨 마지막에 있는 두 값을 빼준다.
            initSum -= (nums[size-1] + nums[size-2]);
        }
        return 0;
    }
};

• 우선 탐색을 시작할 subarray 크기를 구해준다. 0과 1의 개수 중에서 작은 값의 2를 곱한 값으로 시작한다.
• subarray 크기를 고정한 상태에서 슬라이딩 하며 종료 조건을 체크한다.
• 특정 subarray 크기에서 종료되지 않으면, subarray를 2 줄이고 다시 반복한다.

푼 후

• 통과되긴 했는데 속도가 하위 5%다. 메모리는 상위 6.5%여서 위로를 해보지만 그렇기엔 속도가 너무 느리다. 복잡도를 생각했을 때부터 느릴 거라 생각했지만, 다른 아이디어가 떠오르지 않았다. 처음엔 시간 초과 나서 나름 최적화 하긴 했는데, 통과 된 게 신기하다.

2. 구간 합 (prefix sum)

풀기 전

• 다른 사람들이 올린 solution을 참고했다.

코드

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
    	// sum을 키로 갖고, nums의 idx를 값으로 갖는 unordered map을 만든다.
        unordered_map<int, int> sum_idx_map;
        sum_idx_map[0] = -1;  // sum이 0인 경우는 엣지케이스이므로 -1을 직접 넣어준다.
        
        int max_length = 0;

        int sum = 0;
        // nums를 탐색한다.
        for (int i=0; i<nums.size(); i++) {
        	// 값이 0이면 sum에 -1 하고, 1이면 +1 한다.
            if (nums[i] == 0)
                sum--;
            else  // num == 1
                sum++;

			// sum이 map에 없으면 {sum:idx}를 추가해준다.
            if (sum_idx_map.find(sum) == sum_idx_map.end()) {
                sum_idx_map[sum] = i;
            } else {
            	// sum이 map에 있다는 건 이전에 같은 sum이 나온 적이 있다는 거다.
                // 즉, 이전에 sum이 나온 이후로 오르락 내리락 하다가 다시 돌아왔다는 거다.
                // 현재 idx와 이전의 idx 차이를 통해 subarray 크기를 구할 수 있다.
                int sub_length = i - sum_idx_map[sum];
                max_length = max(sub_length, max_length);
            }
        }
        return max_length;
    }
};

• 구간 합을 구한 뒤 hashmap(unordered map)에 저장하는 방식이다.
• 0이 나오면 sum에 1을 빼고, 1이 나오면 1을 더한다.
• sum이 map에 없으면, map에 {sum: idx}로 추가해준다.
• sum이 map에 있으면, subarray를 구할 수 있다. 이전에 같은 sum 값이 나온적 있다는 뜻인데, 그 후로 오르락 내리락 하다가 같은 레벨로 돌아왔다는 의미이다. 그래서 (현재 idx - 이전 idx)로 subarray 크기를 구할 수 있다.
  • 예를 들면, nums=[0, 1, 1, 1, 0]일 때 아래와 같은 과정을 거친다.
    • idx = 0
      nums[0] == 0
      => sum = 0 - 1 = -1
      => map = {0: -1, -1: 0}
    • idx = 1
      nums[1] == 1
      => sum = -1 + 1 = 0
      => map에 0이 있으므로 subarray 크기 구해보면 현재 위치 - 이전 위치 = 1 - (-1) = 2
    • idx = 2
      nums[2] == 1
      => sum = 0 + 1 = 1
      => map = {0: -1, -1: 0, 1: 2}
    • idx = 3
      nums[3] == 1
      => sum = 1 + 1 = 2
      => map = {0: -1, -1: 0, 1: 2, 2: 3}
    • idx = 4
      nums[4] == 0
      => sum = 2 - 1 = 1
      => map에 1이 있으므로 subarray 크기 구해보면 현재 위치 - 이전 위치 = 4 - 2 = 2

푼 후

• 이런 문제는 솔루션을 보면 간단한데 생각해내기가 어려운 거 같다. 특히 subarray에서 그런 경우가 많은 거 같다. 일단 시간 복잡도에서 답이 안 보이면 hashmap을 먼저 떠올려봐야겠다.