LeetCode 17. Letter Combinations of a Phone Number 자바 문제 풀이

문제

LeetCode - The World's Leading Online Programming Learning Platform

문제 해결 방법

• 이 문제는 모든 조합을 찾는 문제입니다.
• 조합을 찾는 문제이므로, 백트래킹 알고리즘을 사용할수 있습니다.

부분문자열과 순열, 그리고 조합의 차이점, 경우의 수란?

• 백트래킹은 가능한 모든 해를 탐색해야 할 때 혹은 모든 가능한 조합을 고려해야 할 때 효율적이며, 위 문제는 가능한 모든 조합을 찾는 문제입니다.

backtracking 알고리즘이란?

• 알고리즘
  • 각 숫자에 대응되는 문자을 어레이에 미리 final로 선언합니다.
  • 0 혹은 null일경우 빈 list를 리턴합니다.
  • 재귀함수를 시작합니다.
  • 한 문자를 선택하여, 시작 가능한 모든 수를 탐색하고, 스트링빌더에 추가합니다.
  • 한 문자를 제거하고 다음문자로 진행하여 반복합니다.

Github Link

https://github.com/eunhanlee/LeetCode_17_LetterCombinationsofaPhoneNumber_Solution.git

시간복잡도: O(3^N * 4^M), 공간복잡도: O(N)

public class Solution {

    /**
     * 각 숫자에 해당하는 키패드 문자들을 매핑한 배열입니다.
     */
    private static final String[] letterMap = {
            "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    /**
     * 주어진 전화번호의 모든 가능한 문자 조합을 생성합니다.
     *
     * @param digits 숫자로 이루어진 전화번호를 나타내는 문자열입니다. (0-9)
     * @return 전화번호의 모든 가능한 문자 조합을 담고 있는 리스트입니다.
     */
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        // 만약 입력이 null이거나 비어있다면, 빈 결과 리스트를 반환합니다.
        if (digits == null || digits.length() == 0) {
            return result;
        }

        // 시작 위치에서 백트래킹을 시작합니다.
        backTracking(result, digits);
        return result;
    }

    /**
     * 백트래킹 과정을 시작하기 위한 보조 메소드입니다.
     *
     * @param result 문자 조합을 저장할 리스트입니다.
     * @param digits 숫자로 이루어진 전화번호를 나타내는 문자열입니다. (0-9)
     */
    private void backTracking(List<String> result, String digits){
        backTrackingRecur(result, new StringBuilder(), digits, 0);
    }

    /**
     * 문자 조합을 생성하기 위한 재귀적인 백트래킹 메소드입니다.
     *
     * @param result 문자 조합을 저장할 리스트입니다.
     * @param sb 현재 문자 조합을 구성하는 StringBuilder입니다.
     * @param digits 숫자로 이루어진 전화번호를 나타내는 문자열입니다. (0-9)
     * @param index 현재 처리 중인 digits 문자열의 인덱스입니다.
     */
    private void backTrackingRecur(List<String> result, StringBuilder sb, String digits, int index) {
        // digits 문자열의 끝에 도달하면 현재 조합을 결과 리스트에 추가하고 반환합니다.
        if (index == digits.length()) {
            result.add(sb.toString());
            return;
        }

        // 현재 숫자와 해당하는 문자들을 가져옵니다.
        char digit = digits.charAt(index);
        String letters = letterMap[digit - '0'];

        // 각 문자를 순회하며 StringBuilder에 추가합니다.
        for (char ch : letters.toCharArray()) {
            sb.append(ch);
            // 다음 숫자의 문자들로 재귀 호출합니다.
            backTrackingRecur(result, sb, digits, index + 1);
            // 마지막에 추가한 문자를 제거하여 백트래킹하고 다른 문자를 시도합니다.
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

설명

시간 복잡도(Time Complexity):

• letterCombinations 메소드의 시간 복잡도는 O(3^N * 4^M)입니다.
  • 여기서 N은 입력 digits의 길이이며, 3과 4는 숫자 2와 7을 제외한 나머지 숫자들이 가지는 문자 수입니다.
  • 각 숫자에 대해서 문자들을 조합하는데 최대 4개의 문자 조합이 필요하며, 총 N개의 숫자가 있으므로 최악의 경우에 4^N의 시간이 걸립니다.
  • 하지만 2와 7의 경우에는 3개의 문자만 가지므로, 총 M개의 2와 7이 있을 때, 3^M의 시간이 걸립니다.
  • 따라서 모든 경우를 합치면 O(3^N * 4^M)의 시간 복잡도가 됩니다.

공간 복잡도(Space Complexity):

• letterCombinations 메소드의 공간 복잡도는 O(N)입니다.
  • 여기서 N은 입력 digits의 길이입니다.
  • 재귀 호출 시마다 StringBuilder sb가 생성되므로, 재귀 호출 스택의 깊이는 최대 N까지 증가합니다.
  • 추가적으로, 최종 결과인 result 리스트에 모든 가능한 문자 조합을 저장하므로, 이 또한 O(N)의 공간을 차지합니다.
  • 따라서 총 공간 복잡도는 O(N)입니다.