LeetCode 2311: 이진수 부분수열 최대 길이 구하기
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
알고리즘
대상자
- 프로그래밍 초보자~중급자
- 이진수 조작 및 그리디 알고리즘 학습자
- 코딩 인터뷰 준비자
핵심 요약
- 모든 '0' 포함: 이진수 값에 영향을 주지 않으므로 무조건 포함
- '1'은 오른쪽부터 그리디하게 추가: 이진수의 가중치가 오른쪽부터 작기 때문
num + pow <= k
조건으로 중단: 이진수 값이k
를 초과하지 않도록 제한
섹션별 세부 요약
1. 문제 정의
- 이진수 문자열
s
와 정수k
를 입력으로 받아,k
이하의 이진수로 구성된 최장 부분수열의 길이를 반환 - 부분수열은 원래 순서를 유지해야 하며, 앞쪽 0은 허용됨
- 예:
s = "1010", k = 5
→101
(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
으로 중단 조건 명확화
결론
- 이진수의 가중치 특성과 그리디 전략을 결합해 효율적인 알고리즘 설계
0
과1
처리 분리가 핵심 →s.count('0')
과 오른쪽 '1' 추가 분리k
의 범위에 따라 처리 로직이 달라지므로, 조건 검사를 꼼꼼히 수행해야 함