제목

카테고리

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

서브카테고리

웹 개발

대상자

- 알고리즘 문제 해결에 관심 있는 개발자

- 재귀, 백트래킹, 문자열 처리 기술을 익히고자 하는 중급 이상 개발자

- LeetCode 또는 코딩 인터뷰 준비자

핵심 요약

• 문자 빈도 분석을 통해 k 번 반복 가능한 문자만 필터링 (cnts[c - 'a'] >= k).
• 역사전순(Reverse lexicographic order) 기반으로 백트래킹을 수행 ('z' → 'a').
• seq * k가 원본 문자열 s의 부분수열(subsequence)인지 검증하는 check 함수 사용.

섹션별 세부 요약

1. 문제 정의 및 접근 방식

• 입력: 문자열 s, 정수 k.
• 목적: k 번 반복 가능한 가장 긴 부분수열 중 사전순 최대인 결과 반환.
• 제약 조건: 각 문자의 빈도가 k 미만인 경우 사용 불가.

2. 알고리즘 단계

• 빈도 분석: cnts[26] 배열을 통해 각 문자의 빈도 계산.
• 필터링: cnts[c - 'a'] >= k 조건에 맞는 문자만 new_s에 포함.
• 백트래킹: 'z'부터 'a'까지 역순으로 문자 추가하며 후보 seq 생성.
• 검증: check(s, k, curr) 함수로 curr * k가 s의 부분수열인지 확인.

3. 코드 구현 예시

• C++: backtrack() 함수에서 cnts[c - 'a'] -= k로 빈도 조정 후 재귀 호출.
• Python: isValid() 함수로 seq가 s의 부분수열인지 검증.
• JavaScript: filtered 배열에 k 이상 빈도의 문자만 포함 후 백트래킹 수행.

4. 효율성 향상 전략

• 예산 가지치기(Pruning): 빈도가 부족한 문자는 탐색 대상에서 제외.
• 역사전순 탐색: 사전순 최대 결과를 우선적으로 탐색.
• 재귀 최적화: curr 길이가 기존 result보다 길면 즉시 업데이트.

결론

• 핵심 팁: 빈도 필터링과 역사전순 백트래킹을 결합하여 효율적으로 탐색.
• 실제 구현: check() 함수로 seq * k의 유효성을 검증하는 것이 핵심.
• 언어 지원: C++, Python, JavaScript 모두 동일한 로직으로 구현 가능.