[알고리즘] Leetcode_17_Letter_Combinations_of_a_Phone_Number

Problem

Solve

• 애를 먹었던 것은 먼저 digits[i]의 range 가 2~9 라는 것을 파악하지 못하고 1, *, 0, #은 어떻게 처리를 해야하나 멍했다.
  ➡️ 그치만 발견을 하고 2부터 9에 해당하는 문자들을 HashMap 에 추가하며 세팅을 해주었다.
• 백트래킹을 이용한 조합을 이용했다. 이때 조합은 중복처리를 해줌으로써 detph와 같아지면 방문여부 체크된 문자만 추가해 주어야 하는 것으로 알고 있었는데, digit의 길이가 2를 넘어가버리면 두 가지 이상의 문자들을 중복 체크를 어떻게 해야할지 난감했다.
  ➡️ 이럴 땐 굳이 인덱스와 visited 를 이용한 방문여부 체크보다는 인덱스와 우리가 조합해야할 문자열을 파라미터로 전달시켜줌으로 인해서 방문여부에 상관없이 depth와 같아지면 해당 문자열을 추가시켜주면 되었다.

import java.util.*;
class Solution {
    public void backtracking(List<String> result, String digits, HashMap<Character, String> map, String current, int idx){
    	//base case
        if(idx == digits.length()){
            result.add(current);
            return;
        }

        char c = digits.charAt(idx); //digits의 숫자 문자 추출
        String str = map.get(c); //숫자에 해당하는 알파벳 문자 추출

        for(int i = 0 ; i < str.length(); i++){
  			//current 에 알파벳 문자 하나씩 추가시켜줌
            backtracking(result, digits, map, current+str.charAt(i), idx+1);
        }
    }
    public List<String> letterCombinations(String digits) {
    	//결과 반환값
        List<String> result = new ArrayList<>();
        
        //문자가 "" 일 때의 처리
        if(digits.length() == 0) return result;
        
        HashMap<Character, String> map = new HashMap<>();

        char[] symbols = {'2', '3', '4', '5', '6', '7', '8', '9'};
        String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        for(int i = 0 ; i < symbols.length ; i++){
            map.put(symbols[i], letters[i]);
        }

        
        backtracking(result,digits, map, "", 0);
        return result;
    }
    
}

그런데 메모리 측면에서 생각해보니 굳이 HashMap 을 써야하나 싶었다.
HashMap<숫자 문자, 알파벳문자열> 대신 String[] 배열을 이용해 숫자 문자 - 2 의 인덱스값은 "알파벳문자열" 원소로 지정하면 될 것 같았다.

import java.util.*;
class Solution {
    public void backtracking(List<String> result, String digits, String[] symbols, String current, int idx){
       if(idx == digits.length()){
           result.add(current);
           return;
       }
       
        String letters = symbols[digits.charAt(idx)-'0'-2];
        //digits의 문자는 char 형 이기 때문에 ASCII 코드를 이용해 int 형으로 변환
        
       for(int i = 0 ; i < letters.length() ; i++){
           backtracking(result, digits, symbols, current+ letters.charAt(i) , idx+1);
       }
       
    }
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits.length() == 0) return result;
        

        String[] symbols = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
      
        
        backtracking(result,digits, symbols, "", 0);
        return result;
    }
    
}

HashMap 사용

배열 사용

그치만 HashMap을 사용하나 배열을 사용하나 공간복잡도 차이는 크게 나지 않았다. 그리고 백트래킹을 사용하는 것은 똑같기 때문에 시간 복잡도도 똑같았다.
결론은 쉽게 하려면 배열을 , 좀 더 깔끔하게 하려면 HashMap 을 사용해야겠다.