17. 전화번호 문자 조합 (Letter Combinations of a Phone Number)
문제 설명
주어진 숫자(2-9)를 이용해 전화번호 버튼에 해당하는 모든 문자 조합을 반환하라. 결과는 어떤 순서로든 상관없다.
입력 및 출력 예시
Example 1:
- Input: digits = "23"
- Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
- Input: digits = ""
- Output: []
Example 3:
- Input: digits = "2"
- Output: ["a","b","c"]
제약사항
- 0 <= digits.length <= 4
- digits[i]는 ['2', '9'] 범위 내의 숫자이다.
문제 해석
- 숫자 문자열 `digits`를 입력받는다.
- `digits`의 길이는 만들 수 있는 문자 조합의 최대 길이와 같다.
- 각 숫자는 전화번호 키패드의 문자와 매핑된다.
- 주어진 숫자 조합으로 만들 수 있는 모든 문자 조합을 리스트 형태로 반환한다.
풀이 1: BFS (Breadth-First Search) 사용
시간 복잡도
- Leetcode 실행시간: 5ms
- 시간복잡도: O(3^n * 4^m) (n은 3개의 문자를 가지는 숫자의 수, m은 4개의 문자를 가지는 숫자의 수)
- 입력받는 digits의 길이는 최대 4이고, 각 숫자가 매핑되는 문자의 최대 조합을 모두 탐색하게 되므로 입력크기 변화에 따른 실행 시간의 변화가 아닌, 최대 가능한 조합 수로 측정하게 된다.
핵심 아이디어
- 책에는 DFS 재귀 방식으로만 풀이가 되어있었는데, 다른 풀이법을 찾아보고 싶었다.
- Queue를 사용하게 되면 선입선출 원칙에 따라 한 개의 문자를 꺼내서 새로운 문자와 조합하고 다시 저장해 주기를 반복하면서 모든 조합을 만들 수 있다.
코드 구현
public List<String> letterCombinations(String digits) {
if (digits.isBlank()) {
return List.of(); // 빈 입력 처리
}
List<String> result = new ArrayList<>();
queue(result, digits);
return result;
}
// 전화번호 키패드의 숫자와 대응되는 문자들을 저장하는 배열
// private static으로 선언하여 클래스 내부 함수에서 참조할 수 있도록 함
private static final String[] KEYS = new String[]{
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
private void queue(List<String> result, String digits) {
// BFS를 위한 큐 초기화
Deque<String> queue = new ArrayDeque<>();
queue.add(""); // 빈 문자를 1개 추가해줌으로써 첫번째 자리의 조합을 만들 수 있는 기반이 됨
// 입력받은 문자의 갯수만큼 반복하며 모든 조합 생성
for (char digit : digits.toCharArray()) {
String letters = KEYS[digit - '0']; // 아스키값을 이용해 문자 '2'에서 숫자 2로 만들어줌
int size = queue.size();
for (int i = 0; i < size; i++) { // 현재 큐 내부의 모든 요소를 꺼내 새롭게 조합
String combination = queue.poll(); // 기존 조합 꺼내기
for (char letter : letters.toCharArray()) {
queue.add(combination + letter); // 꺼낸 요소와 새로운 조합 생성하여 저장
}
}
}
result.addAll(queue); // List의 addAll()을 통해 queue의 요소들을 한번에 추가
}
풀이 과정
- 입력된 숫자 문자열이 비어있는지 확인하고, 비어있다면 빈 리스트를 반환한다.
- Queue 객체를 생성하고 초기화한다. 이때, 첫 번째 자리의 요소 조합을 위해 빈 문자열("")을 한 개 삽입한다.
- Queue의 선입선출의 특성을 이용해 기존 요소를 꺼내 새롭게 올 수 있는 모든 요소와 조합 후 저장하는 과정을 반복한다.
- 최종적으로 큐에 남아있는 모든 조합을 결과 리스트에 추가한다.
고민했던 부분
- Queue의 어떤 부분이 이 문제를 푸는데 적합한 것인지 궁금했다.
- 코드를 실제로 작성해 보면서 기존 요소를 꺼내 새로운 요소들과 전부 조합 후 저장해 주는 과정을 반복하는 것이 풀이가 가능한 지점이라는 것을 느낄 수 있었다.
풀이 2: DFS (Depth-First Search) 사용
시간 복잡도
- Leetcode 실행시간: 0ms
- 시간복잡도: O(3^n * 4^m) (n은 3개의 문자를 가지는 숫자의 수, m은 4개의 문자를 가지는 숫자의 수)
핵심 아이디어
- 사람이 생각하기에 조합할 수 있는 문자를 위에서부터 아래로 쌓은 뒤 선을 그으며 조합을 생각하는 방식과 유사한 DFS(재귀) 방식으로 풀어보자.
코드 구현
public List<String> letterCombinations(String digits) {
if (digits.isBlank()) {
return List.of();
}
List<String> result = new ArrayList<>();
dfs(digits, 0, new StringBuilder(), result); // 입력받은 digits의 0번째 문자부터 시작
return result;
}
private static final String[] KEYS = new String[]{
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
private void dfs(String digits, int index, StringBuilder path, List<String> result) {
if (digits.length() == path.length()) { // 재귀를 멈춰야 하는 기준
result.add(path.toString()); // 현재 조합의 길이가 입력 문자열의 길이와 같으면 결과 리스트에 추가
return;
}
String letters = KEYS[digits.charAt(index) - '0']; // 현재 인덱스의 숫자에 대응하는 문자들 가져오기
for (char c : letters.toCharArray()) { // 각 문자에 대해 재귀적으로 조합 생성
dfs(digits, index + 1, new StringBuilder(path).append(c), result);
// path.deleteCharAt(index); // path 객체를 재사용하는 경우 직접 마지막 문자를 제거해야 함
}
}
풀이 과정
- 입력된 숫자 문자열이 비어있는지 확인하고, 비어있다면 빈 리스트를 반환한다.
- index를 사용해 탐색할 digits의 문자 위치를 움직인다.
- 계속해서 깊이 탐색하다, 탐색하던 문자열의 길이가 최대 길이(digits 길이)와 같아지면 저장 후 재귀를 멈춘다.
- 재귀를 빠져나왔을 때 for문을 통해 다음 문자와의 조합 후 재귀를 시도한다.
- 재귀가 끝나면 상위 for문에 대해 문자열 순회를 반복하며 재귀를 종료한다.
- 최종적으로 완성된 조합을 결과 리스트에 추가한다.
고민했던 부분
- 어떤 지점에서 어떻게 한 단계 더 깊이 들어갈 것인가? => 입력받은 digits의 번호를 순회하면서 해당하는 문자열의 각 문자별로 재귀가 필요했다.
- 재귀 종료의 기준은 어떻게 새울 것인가? => 명확하게 길이의 제한을 둘 수 있었다.
- StringBuilder 인스턴스인 path 변수는 재사용할 것인가? => 최대 조합의 수가 많지 않고 코드의 가독성 측면이나 코드를 재활용함으로써 발생할 수 있는 문제, 추가적으로 메서드를 사용해야 하는 부분 때문에 신규 인스턴스를 만들어 주었다.
결론
- 학습 내용: 이번 문제를 통해 BFS와 DFS를 활용한 문자열 조합 생성 방법을 학습했다. BFS는 큐를 사용하여 레벨별로 순차적으로 조합을 생성하고, DFS는 재귀 호출을 통해 깊이 우선으로 조합을 생성하는 방법이다.
- 향후 계획: 앞으로 더 복잡한 문자열 조합 문제를 풀 때, 두 가지 방법을 적절히 사용하여 문제를 해결할 수 있도록 연습할 예정이다.
<현재 공부 중인 알고리즘 도서>
'Java > Algorithm' 카테고리의 다른 글
LeetCode #77. Combinations(조합) 2가지 DFS로 풀어보자! (0) | 2024.08.06 |
---|---|
LeetCode #46. Permutations(순열) DFS(백트래킹, 재귀)로 풀어보자! (0) | 2024.08.03 |
LeetCode # 347. HashMap과 PriorityQueue, Stream을 이용해 풀어보자 (0) | 2024.07.24 |
댓글