프로그래밍/소프트웨어 개발: **Lexicographically Smallest Equivalent String 문제 해결 가이드**

카테고리

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

서브카테고리

알고리즘

대상자

- 초보 프로그래머 및 알고리즘 학습자

- DSU(Union-Find)와 문자열 조작 기초를 익히고자 하는 사람들

- 중간 난이도의 알고리즘 문제 풀이에 관심 있는 학습자

핵심 요약

• DSU(Union-Find) 알고리즘을 활용해 등가 관계를 처리하고, 사전 순으로 가장 작은 문자를 찾는 방법을 설명
• s1과 s2의 각 인덱스 쌍을 기반으로 등가 관계 그래프를 생성하고, 부모 노드를 항상 사전 순 작은 문자로 설정
• baseStr의 각 문자를 해당 그래프의 루트 노드(사전 순 최소 문자)로 변환하여 결과 생성

섹션별 세부 요약

1. 문제 정의 및 등가 관계

• s1과 s2의 동일 인덱스 문자는 등가 관계로 연결
• 등가 관계는 반사, 대칭, 추이성을 만족
• baseStr의 각 문자를 해당 등가 그룹의 사전 순 최소 문자로 대체

2. DSU 구조 설계

• 각 문자를 노드로, s1[i]와 s2[i]를 간선으로 연결
• findPar() 함수로 루트 노드 찾기
• unionByLex() 함수로 사전 순 작은 문자를 부모로 설정
• parent 배열은 26개 알파벳을 관리

3. 코드 구현 예시

• C++: DSU 클래스를 사용해 findPar() 및 unionByLex() 구현
• JavaScript: 배열 parent와 재귀적 find() 및 union() 함수 사용
• Python: parent 리스트와 find() 및 union() 함수를 정의
• 공통 로직: s1과 s2의 쌍을 처리 후 baseStr의 각 문자를 루트 노드로 변환

4. 테스트 케이스 및 성능

• 입력 예시: s1 = "parker", s2 = "morris", baseStr = "parser" → "makkek"
• 시간 복잡도: O(n + m) (n = s1 길이, m = baseStr 길이)
• 공간 복잡도: O(1) (26개 알파벳만 저장)

결론

• DSU 알고리즘은 등가 관계를 효율적으로 처리하는 핵심 도구
• 사전 순 최소 문자를 선택하기 위해 부모 노드를 항상 작은 문자로 설정
• 실무에서 유사한 문제(예: 문자 집합 간 매핑)에 적용 가능하며, 시간 복잡도 O(n + m)으로 최적화 가능