최대 합을 가지는 길이 k의 부분 수열 찾기
프로그래밍/소프트웨어 개발
개발 툴
대상자
- 소프트웨어 개발자, 알고리즘 문제 풀이자, 자바 프로그래머
- 중간 난이도 – 알고리즘 이해와 자바의 자료구조 사용에 대한 기본 지식 필요
핵심 요약
- k개의 최대 요소를 선택해야 하며, 원래 배열의 순서를 유지해야 한다
- 최소 힙(min-heap)을 사용하여 k개의 최대 요소를 추적
- TreeMap을 사용하여 원래 인덱스에 따라 정렬된 결과 배열 생성
섹션별 세부 요약
1. 문제 정의 및 예시
- 문제는 주어진 배열에서 길이 k의 부분 수열 중 합이 가장 큰 것을 찾는 것
- 부분 수열은 원래 배열의 요소 순서를 유지하며, 일부 요소를 삭제한 형태
- 예시 1: nums = [2,1,3,3], k = 2 → [3,3] (합 = 6)
2. 알고리즘 전략
- k개의 최대 값을 선택해야 하므로, 단순 정렬은 불가능
- 최소 힙(min-heap)을 사용하여 k개의 최대 요소를 추적
- 힙 크기가 k를 초과하면 최소 요소를 제거
3. 구현 방법
- PriorityQueue를 사용하여 [value, index] 형태의 요소를 저장
- TreeMap을 사용하여 원래 인덱스에 따라 정렬
- TreeMap의 키 순서에 따라 결과 배열을 생성
4. 시간 복잡도
- O(n log k) – n개의 요소를 힙에 삽입
- O(k log k) – TreeMap 삽입 및 정렬
- O(k) – 결과 배열 생성
- 전체 시간 복잡도: O(n log k + k log k)
5. 공간 복잡도
결론
- 최소 힙과 TreeMap을 활용하여 최대 합을 가진 부분 수열을 생성
- 원래 배열의 순서를 유지하면서 k개의 최대 요소를 선택해야 하므로, 자료구조의 적절한 사용이 중요
- Java의 PriorityQueue와 TreeMap을 사용하여 효율적으로 문제를 해결할 수 있음
subsequence
algorithm
array
k
priority queue
heap
tree map