제목

카테고리

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

서브카테고리

웹 개발

대상자

• 알고리즘 문제 해결에 관심 있는 개발자
• 중간 수준 (힙, 그리디 알고리즘 이해 필요)

핵심 요약

• 문제 목표: *와 그에 대응하는 최소 문자를 제거하여 사전순 최소 문자열 생성
• 핵심 알고리즘:

- min-heap으로 현재까지 만나는 가장 작은 문자 추적

- * 처리 시 heap에서 최소 문자 선택 및 삭제

- !로 삭제된 문자 표시 후 최종 문자열 구성

• 시간 복잡도: O(n log k) (k ≤ 26, 26개 알파벳)
• 공간 복잡도: O(n) (문자 위치 추적 및 삭제 표시)

섹션별 세부 요약

1. 문제 설명

• 입력 문자열 s는 소문자와 * 포함
• * 처리 규칙:

- *의 왼쪽에 있는 가장 작은 문자 제거 (다중 동일 문자 시 임의 선택)

- *와 제거된 문자 모두 최종 결과에서 제외

• 예시: "aaba*" → "aab" (마지막 'a' 제거)

2. 알고리즘 접근

• 핵심 전략:

- min-heap으로 각 알파벳의 최소 문자 추적

- indices[26] 배열로 각 문자의 위치 기록

- * 처리 시 heap에서 최소 문자 선택 후 !로 표시

• 구현 단계:

1. *이 아닌 문자를 heap에 삽입, indices에 위치 기록
2. * 발견 시 heap에서 최소 문자 선택 및 삭제
3. !로 표시된 문자 필터링하여 최종 문자열 구성

3. 코드 구현 (C++, JavaScript, Python)

• C++:

- priority_queue 사용

- indices[26] 벡터로 위치 기록

- !로 삭제 표시 후 필터링

• JavaScript:

- pq.sort() 기반 간단한 힙 구현

- indices 배열로 위치 추적

- filter로 ! 제거

• Python:

- heapq 모듈 사용

- defaultdict(list)로 위치 기록

- join으로 ! 제거

4. 예시 및 테스트 케이스

• "zzyyaa" → "zya" (각 전 최소 문자 제거)
• "aaabbbc" → "aabb" (첫 번째 전 'a', 두 번째 전 'b' 제거)

결론

• 실무 팁:

- min-heap과 index tracking을 활용한 그리디 알고리즘 적용

- * 처리 시 최소 문자 선택을 통해 사전순 최소 결과 생성

- 대규모 입력 처리 시 O(n log k) 복잡도의 효율성 확보