가장 큰 합을 가진 길이 K의 부분 수열 찾기 – LeetCode 2099 문제 요약

카테고리

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

서브카테고리

데이터 분석

대상자

알고리즘 문제 해결에 관심 있는 개발자, 중급 이상의 프로그래밍 실력이 있는 사람들

핵심 요약

• nth_element 또는 최소 힙으로 임계값을 결정하여, 상위 k 개의 요소를 선택
• 임계값 이상의 요소와 동일한 값의 요소 수를 계산하여 중복을 처리
• 원본 배열 순서를 유지하면서 결과 수열을 재구성

섹션별 세부 요약

1. 임계값 설정

• nth_element 함수를 사용하여 상위 k 개의 요소 중 가장 작은 값을 임계값으로 설정
• 최소 힙을 활용해 동일한 작업 수행 가능

2. 요소 빈도 계산

• 임계값보다 큰 요소의 수(larger)와 임계값과 같은 요소의 수(equal)를 계산
• equal은 k - larger로 결정

3. 결과 수열 재구성

• 원본 배열을 순회하며, 임계값 이상의 요소를 우선 선택
• 동일한 값은 equal 수만큼만 포함
• 순서를 유지하면서 k 개의 요소를 모으고 종료

4. 시간 및 공간 복잡도

• 시간 복잡도: O(n) (선택 + 재구성)
• 공간 복잡도: O(n) (보조 배열/카운터 사용)

결론

• 중복된 임계값 요소 처리와 원본 배열 순서 유지가 핵심
• nth_element 또는 heapq.nlargest 활용으로 효율적인 선택 가능
• 예시 코드에서 JavaScript는 정렬 후 슬라이싱, Python은 heapq 활용 등 언어별 구현 차이 존재