비트 OR 임계치를 넘는 가장 짧은 구간

자바스크립트 코딩테스트 문제로 bitwise-window 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard bitwise-window 함수명: solution 제한 시간: 300ms

0 이상의 정수 배열 nums와 목표값 target이 주어질 때, 비트 OR 값이 target 이상이 되는 가장 짧은 연속 구간의 시작 인덱스와 끝 인덱스를 반환하는 solution 함수를 작성하세요.

길이가 같은 후보가 여러 개라면 시작 인덱스가 더 작은 구간을 반환합니다. 그런 구간이 없으면 [-1, -1]을 반환하면 됩니다.

제한사항

• 1 <= nums.length <= 100000
• 0 <= nums[i] <= 1000000000
• 1 <= target <= 1000000000
• 반환값은 [start, end] 형태의 길이 2 배열입니다.
• 비트 OR은 각 비트 위치에서 하나라도 1이면 결과 비트가 1이 됩니다.
• 연속 구간은 비어 있을 수 없습니다.

예시

• 입력:
  • nums = [1, 2, 4, 1]
  • target = 7 → 출력: [0, 2]
• 입력:
  • nums = [1, 2, 4, 2]
  • target = 6 → 출력: [1, 2]
• 입력:
  • nums = [8, 1, 2, 7]
  • target = 7 → 출력: [0, 0]
• 입력:
  • nums = [1, 1, 1]
  • target = 8 → 출력: [-1, -1]

힌트

• 왼쪽 포인터를 줄여 가는 슬라이딩 윈도우를 떠올릴 수 있지만, 합과 달리 비트 OR은 원소 하나를 빼도 값이 바로 되돌아가지 않습니다.
• 어떤 비트가 현재 구간 안에 몇 번 등장했는지 세고 있으면, 왼쪽 원소를 제거할 때 그 비트가 아직 살아 있는지 판단할 수 있습니다.
• 현재 구간의 OR 값을 직접 다시 전부 계산하지 말고, 비트 카운트를 바탕으로 갱신해 보세요.

해설

이 문제는 겉보기에는 평범한 투 포인터처럼 보이지만, 핵심 장애물은 비트 OR 연산이 쉽게 되돌릴 수 없다는 점입니다.

합(sum) 문제라면 오른쪽을 늘릴 때 더하고 왼쪽을 줄일 때 빼면 됩니다. 하지만 OR은 다릅니다. 예를 들어 구간 OR이 7이고 왼쪽 원소를 제거해도, 어떤 비트는 다른 원소 덕분에 여전히 1일 수 있고 어떤 비트는 사라질 수 있습니다.

그래서 이 문제는 각 비트가 현재 윈도우 안에 몇 개 들어 있는지 함께 관리해야 합니다.

1) 오른쪽 포인터를 늘리며 비트 카운트 추가

nums[right]를 구간에 포함할 때, 켜져 있는 비트들을 확인해서 해당 비트 카운트를 1씩 늘립니다.

• 어떤 비트의 카운트가 0 → 1이 되면, 그 비트는 이제 현재 구간 OR에 새로 반영되어야 합니다.
• 따라서 currentOr에도 그 비트를 켭니다.

2) 조건을 만족하면 왼쪽 포인터를 줄여 본다

현재 currentOr >= target이면, 지금 구간은 후보입니다.

이때:

1. 길이가 더 짧으면 정답 갱신
2. 길이가 같다면 시작 인덱스가 더 작은지 비교
3. 그다음 nums[left]를 구간에서 제거하고 left를 한 칸 이동

원소를 제거할 때는 그 원소가 갖고 있던 비트들의 카운트를 줄입니다. 어떤 비트의 카운트가 1 → 0이 되면, 이제 현재 구간 안에는 그 비트를 켜 줄 원소가 하나도 없다는 뜻이므로 currentOr에서 그 비트를 꺼야 합니다.

3) 왜 이 방식이 가능한가?

비트 위치는 최대 30개 정도만 보면 됩니다. nums[i], target이 10^9 이하이므로 이진수 비트 수가 많지 않기 때문입니다.

즉, 각 원소를 추가하거나 제거할 때 해야 할 일은:

• 최대 30개 비트를 확인하고
• 카운트를 갱신하고
• 필요한 비트만 켜거나 끄는 것 뿐입니다.

그래서 전체 시간 복잡도는 O(비트수 * n) 정도이며, 여기서는 사실상 O(n)처럼 사용할 수 있습니다.

4) 구현 포인트

• bitCount[bit]: 현재 윈도우에서 해당 비트가 켜진 원소 수
• currentOr: 현재 윈도우의 OR 값
• left, right: 슬라이딩 윈도우 경계
• 정답은 [bestStart, bestEnd]로 관리

5) 예시로 보기

nums = [1, 2, 4, 2], target = 6을 보겠습니다.

• right = 0 → 구간 [0, 0], OR = 1
• right = 1 → 구간 [0, 1], OR = 3
• right = 2 → 구간 [0, 2], OR = 7 → 조건 만족
  • 후보 [0, 2]
  • 왼쪽 1 제거 → 구간 [1, 2], OR = 6
  • 여전히 조건 만족 → 더 짧은 후보 [1, 2]
  • 다시 왼쪽 2 제거 → 구간 [2, 2], OR = 4 → 조건 불만족

최종 정답은 [1, 2]입니다.

이 문제의 핵심은 OR 자체를 되돌리려 하지 말고, 비트의 생존 여부를 카운트로 관리하는 것입니다. 이 아이디어를 잡으면 hard답게 까다롭지만 구현은 비교적 깔끔하게 정리할 수 있습니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

입력값 []

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.