DSA 패턴 — 단어에서 공통 문자 찾기

카테고리

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

서브카테고리

데이터 분석

대상자

- 개발자 (특히 알고리즘 문제 해결, 문자열 처리 관련)

- 난이도: 중간 (빈도 맵 개념과 최소값 계산 기법 필요)

핵심 요약

• 빈도 맵(frequency map)을 사용해 각 단어의 문자 빈도를 계산하고, 모든 단어에서 공통된 문자를 찾는다.
• 최소 빈도(minimum count)를 기반으로 결과를 생성하며, 이는 공통 문자의 중복 횟수도 포함한다.
• 시간 복잡도: O(N * K) (N = 단어 수, K = 평균 단어 길이), 공간 복잡도: O(1) (최대 26개의 알파벳만 사용).

섹션별 세부 요약

1. 문제 정의 및 예시

• 주어진 단어 배열에서 모든 단어에 포함된 문자 (중복 포함)를 찾는 문제이다.
• 예: ["bella", "label", "roller"] → ["e", "l", "l"]
• 문자 중복은 각 단어의 최소 빈도로 결정된다.

2. 알고리즘 핵심 단계

• 첫 번째 단어의 빈도 맵을 초기화 (예: array_count_values(str_split($words[0]))).
• 나머지 단어를 순회하며, 현재 단어의 빈도 맵과 비교해 최소값을 업데이트.
• 빈도 맵에서 존재하지 않는 문자는 제거 (예: unset($freq[$char])).

3. 결과 생성

• 최종 빈도 맵에서 문자별 빈도에 따라 결과 배열 생성 (예: for ($i = 0; $i < $count; $i++) $result[] = $char).

결론

• PHP의 array_count_values() 및 str_split() 함수를 활용해 빈도 맵을 생성하고, 최소값을 기반으로 결과를 재구성하는 패턴을 적용.
• 공통 문자 추출 문제에 재사용 가능한 알고리즘으로, "모든 단어에 포함된 문자" 조건의 핵심 해결 방법.