최장 조화 부분 수열 LeetCode 594 (C++, JavaScript, Python)
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
데이터 분석
대상자
- *중급 이상의 알고리즘 개발자** (해시맵 활용 및 빈도 분석 기술 필요)
- *난이도**: 중간 (데이터 구조 이해 필요)
핵심 요약
- 빈도맵(freq map)을 활용해 모든 부분 수열 생성 없이 최적화된 계산
- 연속 수 쌍(num, num+1)만 검사해 시간 복잡도 O(n) 달성
freq[num] + freq[num+1]
계산으로 최장 조화 수열 길이 도출
섹션별 세부 요약
1. 문제 정의 및 접근 방식
- 조화 부분 수열: 최대값-최소값 차가 1인 수열
- 모든 부분 수열 생성 대신 빈도 분석으로 시간 복잡도 최적화
freq[x] + freq[x+1]
계산으로 최대 길이 추출
2. 구현 예시 (C++)
unordered_map
로 빈도 카운팅freq.count(key + 1)
으로 연속 수 존재 여부 확인res = max(res, val + freq[key + 1])
로 최대값 업데이트
3. 구현 예시 (JavaScript)
Map()
객체로 빈도 저장freq.has(key + 1)
으로 연속 수 존재 여부 확인Math.max(res, val + freq.get(key + 1))
로 최대값 계산
4. 구현 예시 (Python)
collections.Counter
로 빈도 카운팅if num + 1 in freq
조건으로 연속 수 검사max(res, freq[num] + freq[num + 1])
로 최대값 업데이트
결론
- *해시맵 기반 빈도 분석**을 통해 지수 시간 복잡도를 회피하고 O(n) 시간에 문제 해결 가능.
- *핵심 팁**: 연속 수 쌍만 검사하는 전략을 활용해 알고리즘 효율성 극대화.