LeetCode 2311: 이진수 부분수열 최대 길이 구하기
AI Store에서 AI코딩으로 만들어진 앱을 만나보세요!
지금 바로 방문하기

LeetCode 2311: 이진수 부분수열 최대 길이 구하기

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

알고리즘

대상자

  • 프로그래밍 초보자~중급자
  • 이진수 조작 및 그리디 알고리즘 학습자
  • 코딩 인터뷰 준비자

핵심 요약

  • 모든 '0' 포함: 이진수 값에 영향을 주지 않으므로 무조건 포함
  • '1'은 오른쪽부터 그리디하게 추가: 이진수의 가중치가 오른쪽부터 작기 때문
  • num + pow <= k 조건으로 중단: 이진수 값이 k를 초과하지 않도록 제한

섹션별 세부 요약

1. 문제 정의

  • 이진수 문자열 s와 정수 k를 입력으로 받아, k 이하의 이진수로 구성된 최장 부분수열의 길이를 반환
  • 부분수열은 원래 순서를 유지해야 하며, 앞쪽 0은 허용됨
  • 예: s = "1010", k = 5101 (5) → 길이 3

2. 핵심 알고리즘

  • '0'은 무조건 포함: s.count('0')로 처리
  • '1'은 오른쪽부터 추가: pow *= 2로 가중치 계산
  • 중단 조건: num + pow > k일 때 반복 중단
  • 시간 복잡도: O(n) (문자열 길이 n)

3. 언어별 구현

  • C++/JavaScript/Python:

```cpp

for (int i = s.length() - 1; i >= 0 && num + pow <= k; --i) {

if (s[i] == '1') {

oneCount++;

num += pow;

pow *= 2;

}

}

```

```python

for i in range(len(s)-1, -1, -1):

if s[i] == '1' and num + pow_ <= k:

one_count += 1

num += pow_

pow_ *= 2

else:

break

```

4. 효율성 및 핵심 원칙

  • 브루트포스 회피: 부분수열 생성 없이 그리디 전략으로 O(n) 시간
  • 이진수 성질 활용: 오른쪽 '1'이 더 작은 영향을 미침
  • 정확한 조건 처리: num + pow <= k으로 중단 조건 명확화

결론

  • 이진수의 가중치 특성그리디 전략을 결합해 효율적인 알고리즘 설계
  • 01 처리 분리가 핵심 → s.count('0')과 오른쪽 '1' 추가 분리
  • k의 범위에 따라 처리 로직이 달라지므로, 조건 검사를 꼼꼼히 수행해야 함