LeetCode 2311: 이진 문자열을 이용한 최장 부분 수열 길이 결정 (K 이하)

핵심 기술

LeetCode 2311 문제는 주어진 이진 문자열 s에서 값이 k 이하인 가장 긴 부분 수열(subsequence)의 길이를 찾는 문제입니다. 핵심은 이진수의 가중치 속성을 활용한 탐욕적(greedy) 접근 방식입니다.

기술적 세부사항

• 문제 정의: 이진 문자열 s와 정수 k가 주어졌을 때, s의 부분 수열 중 k보다 작거나 같은 값을 가지는 가장 긴 부분 수열의 길이를 반환합니다.
• 부분 수열 조건: 원래 순서를 유지해야 하며, 앞에 0이 오는 것도 허용됩니다.
• 최대 길이 확보 전략:
  • 모든 '0'은 값 증가에 영향을 주지 않으므로 부분 수열에 포함시킵니다.
  • '1'은 오른쪽부터 탐욕적으로 선택합니다. 이진수의 가중치는 오른쪽에서 왼쪽으로 갈수록 작아지므로, 오른쪽의 '1'을 먼저 포함시키는 것이 총 길이를 늘리는 데 유리합니다.
  • 이진수의 값이 k를 초과하면 '1' 추가를 중단합니다.
• 구현 (Python 예시):
  python class Solution: def longestSubsequence(self, s: str, k: int) -> int: one_count = 0 num = 0 pow_ = 1 for i in range(len(s) - 1, -1, -1): if s[i] == '1': # 현재 숫자에 pow_를 더해도 k를 초과하지 않는 경우에만 포함 if num + pow_ <= k: one_count += 1 num += pow_ pow_ *= 2 # 다음 비트의 가중치로 업데이트 # k를 초과하면 더 이상 오른쪽 '1'을 추가하지 않음 else: break # '0'의 개수 + 선택된 '1'의 개수 반환 return s.count('0') + one_count
• 시간 복잡도: 문자열의 길이 N에 대해 O(N)입니다. 문자열을 한 번 순회하며 연산합니다.
• 공간 복잡도: O(1)입니다.

개발 임팩트

• 효율적인 문제 해결: 무차별 대입(brute-force) 방식 대신 이진수의 속성을 활용하여 효율적인 알고리즘을 설계할 수 있습니다.
• 탐욕적 사고방식: 주어진 제약 조건 하에서 최적의 해를 얻기 위해 지역적으로 최적의 선택을 하는 탐욕적 알고리즘 설계 능력을 향상시킬 수 있습니다.
• 비트 연산 활용 능력: 이진수의 표현 및 연산에 대한 이해를 심화하고 실제 문제에 적용하는 능력을 기를 수 있습니다.

커뮤니티 반응

• 문제 해결 접근 방식이 간결하고 직관적이라는 평가가 많습니다.
• 이진수의 가중치 특성을 이해하는 것이 핵심임을 강조합니다.
• 코딩 테스트에서 흔히 접할 수 있는 유형의 문제로, 준비에 도움이 된다는 의견이 있습니다.