리트코드) 17.전화번호 문자 조합(자바)

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

문제 : 2에서 9까지 숫자가 주어졌을 때 전화번호로 조합 가능한 모든 문자를 출력하라
키패드가 주어지고 각각 매칭되는 문자가 있음

1()	2(abc)	3(def)
4(ghi)	5(jkl)	6(mno)
7(pqrs)	8(tuv)	9(wxyz)
\*(+)	0(_)	#(^)

• 모든 문자를 출력해야하기 때문에 모든 경우의 수를 다 탐색해야 한다.
• 완전탐색으로도 가능하지만 DFS로 푼다면 한번 갔던 길은 다시 가지 않아도 된다.

import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

class Solution {

    ArrayList<String> result; 
    HashMap<String, List<String>> map;
    String d;
   
    public List<String> letterCombinations(String digits) {
        result = new ArrayList<String>();
        // 예외처리
        if(digits.length() == 0) {
            return result;
        }

        // MAP 셋팅
        map = new HashMap<>();
        map.put("2", Arrays.asList("a","b","c"));
        map.put("3", Arrays.asList("d","e","f"));
        map.put("4", Arrays.asList("g","h","i"));
        map.put("5", Arrays.asList("j","k","l"));
        map.put("6", Arrays.asList("m","n","o"));
        map.put("7", Arrays.asList("p","q","r","s"));
        map.put("8", Arrays.asList("t","u","v"));
        map.put("9", Arrays.asList("w","x","y","z"));

        d = digits;
        dfs(0, new StringBuilder()); // dfs시작

        return result;
    }   

    public void dfs(int idx, StringBuilder path) {
        if(path.length() == d.length()) { // 한바퀴 돌았으면 입력 "ad"
            result.add(path.toString());
            return;
        }

        for(String s : map.get(String.valueOf(d.charAt(idx)))) { // map에서 "a", "b", "c" 
            dfs(idx+1, new StringBuilder(path).append(s));
        }
    }

}

• new StringBuilder()로 매번 새로운 인스턴스를 만들어 주는 이유는 이것이 글자를 생성하고 저장하는 용도이기 때문이다. (매번 비워준다고 생각하면 됨)