Java/Algorithm

LeetCode # 17. Letter Combinations of a Phone Number / DFS(재귀), BFS(Queue)를 이용해 풀어보자

개발자 May 2024. 8. 2.

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의 요소들을 한번에 추가
}

풀이 과정

  1. 입력된 숫자 문자열이 비어있는지 확인하고, 비어있다면 빈 리스트를 반환한다.
  2. Queue 객체를 생성하고 초기화한다. 이때, 첫 번째 자리의 요소 조합을 위해 빈 문자열("")을 한 개 삽입한다.
  3. Queue의 선입선출의 특성을 이용해 기존 요소를 꺼내 새롭게 올 수 있는 모든 요소와 조합 후 저장하는 과정을 반복한다.
  4. 최종적으로 큐에 남아있는 모든 조합을 결과 리스트에 추가한다.

고민했던 부분

  • 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 객체를 재사용하는 경우 직접 마지막 문자를 제거해야 함
    }
}

풀이 과정

  1. 입력된 숫자 문자열이 비어있는지 확인하고, 비어있다면 빈 리스트를 반환한다.
  2. index를 사용해 탐색할 digits의 문자 위치를 움직인다.
  3. 계속해서 깊이 탐색하다, 탐색하던 문자열의 길이가 최대 길이(digits 길이)와 같아지면 저장 후 재귀를 멈춘다.
  4. 재귀를 빠져나왔을 때 for문을 통해 다음 문자와의 조합 후 재귀를 시도한다.
  5. 재귀가 끝나면 상위 for문에 대해 문자열 순회를 반복하며 재귀를 종료한다.
  6. 최종적으로 완성된 조합을 결과 리스트에 추가한다.

고민했던 부분

  • 어떤 지점에서 어떻게 한 단계 더 깊이 들어갈 것인가? => 입력받은 digits의 번호를 순회하면서 해당하는 문자열의 각 문자별로 재귀가 필요했다.
  • 재귀 종료의 기준은 어떻게 새울 것인가? => 명확하게 길이의 제한을 둘 수 있었다.
  • StringBuilder 인스턴스인 path 변수는 재사용할 것인가? => 최대 조합의 수가 많지 않고 코드의 가독성 측면이나 코드를 재활용함으로써 발생할 수 있는 문제, 추가적으로 메서드를 사용해야 하는 부분 때문에 신규 인스턴스를 만들어 주었다.

결론

  • 학습 내용: 이번 문제를 통해 BFS와 DFS를 활용한 문자열 조합 생성 방법을 학습했다. BFS는 큐를 사용하여 레벨별로 순차적으로 조합을 생성하고, DFS는 재귀 호출을 통해 깊이 우선으로 조합을 생성하는 방법이다.
  • 향후 계획: 앞으로 더 복잡한 문자열 조합 문제를 풀 때, 두 가지 방법을 적절히 사용하여 문제를 해결할 수 있도록 연습할 예정이다.

<현재 공부 중인 알고리즘 도서>

자바 알고리즘 인터뷰 with 코틀린 (박상길 저)

댓글