0. 문제

주어진 nums 배열에서 비트 단위 AND 연산(&) 결과가 0이 되는 가장 긴 연속된 부분 배열(subarray)을 찾아야 합니다.

즉, 특정 부분 배열 [nums[l], nums[l+1], ..., nums[r]]에 대해 모든 서로 다른 두 원소의 AND 연산 결과가 0이 되어야 합니다.
또한, 길이가 1인 부분 배열은 항상 "nice"하다고 가정합니다.

예제 1

• 입력: nums = [1,3,8,48,10]

• 출력: 3

• 설명:
  최장 "nice" 서브배열: [3, 8, 48]

  3 & 8 = 0
  3 & 48 = 0
  8 & 48 = 0

  따라서, 길이는 3.

예제 2

• 입력: nums = [3,1,5,11,13]
• 출력: 1
• 설명:
  어떤 인접한 두 숫자를 선택해도, & 연산 결과가 0이 되지 않음.
  따라서 길이 1인 서브배열만 가능

제한사항

1 <= nums.length <= 105
1 <= nums[i] <= 109

1. 문제점

• 시간복잡도: $O(N^2)$
• 슬라이딩 윈도우를 어떻게 사용해야 하는지 감을 못잡음.
• 비트 연산의 특성을 활용하지 못함.

class Solution {
    public int longestNiceSubarray(int[] nums) {
        int longest = 0;
        int currentLong = 0;
        int subTotal = 0;
        int subOr = 1;

        for (int i = 0; i < nums.length; i++) {
            subTotal += nums[i];
            subOr = subOr | nums[i];
            if (subTotal == subOr)
                currentLong++;
            else {
                longest = Math.max(longest, currentLong);
                subTotal = nums[i];
                subOr = nums[i];
                currentLong = 1;
            }
        }
        return Math.max(longest, currentLong);
    }
}

2. 풀이

핵심 아이디어

• "nice"한 subarray에 있는 모든 숫자는 서로 겹치는 비트가 있어서는 안됨. subOr은 현재 각 숫자들이 이미 선점한 비트를 의미하는데, (subOr & nums[right]) != 0이라면, nums[right]가 기존 숫자와 겹치는 비트를 가지고 있다는 의미.
• 슬라이딩 윈도우를 통해 비트가 겹치지 않는 subarray의 범위를 조정해나감. 비트가 겹치는 right를 발견하면 left의 범위를 조정하고 이 때의 범위를 longest와 비교해 가장 긴 경우 탐색.
  이때의 시간복잡도 $O(N)$
• XOR 연산(두 비트가 같으면 0, 다르면 1을 반환)을 통해 nums[left] 요소를 subOr에서 삭제가능.

class Solution {
    public int longestNiceSubarray(int[] nums) {
        int left = 0;
        int subOr = 0; // 현재 부분 배열의 OR 값
        int longest = 0;

        for (int right = 0; right < nums.length; right++) {
            // 만약 현재 OR 값과 새로운 값이 겹치면, left를 이동
            while ((subOr & nums[right]) != 0) {
                subOr ^= nums[left]; // 왼쪽 요소 제거
                left++; // 윈도우 이동
            }

            subOr |= nums[right]; // 새로운 값 추가
            longest = Math.max(longest, right - left + 1); // 현재 길이 업데이트
        }

        return longest;
    }
}