[자바 알고리즘 인터뷰] 12장 그래프 (2) 전화번호 문자 조합

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

 

- 2에서 9까지 숫자가 주어졌을 때 전화번호로 조합 가능한 모든 문자를 출력하라 

 

 

풀이 1) 모든 조합 탐색 

 

-모두 조합하는 형태로 전체를 탐색한 후 백트래킹하면서 결과를 조합할 수 있다.

- digits는 입력값이며, 각 자릿수에 해당하는 키판 배열을 DFS로 탐색하면 결과가 완성된다, 

 

출처: 자바 알고리즘 인터뷰 with 코틀린 저자:박상길 <책만>

 

- 입력값인 digits의 자릿수 단위로 반복하고, 현재 자리 숫자에 해당하는 모든 문자를 탐색하면서 지금까지 구성된 문자열을 path 변수에 저장해 넘기면서 재귀 탐색한다. 

 

public void dfs(List<String> result, Map<Character,List<Character>> dic, String digits, int index, StringBuilder path)
    {
        //끝까지 탐색했으면 결과를 저장하고 리턴
        if(path.length() == digits.length()) {
            result.add(String.valueOf(path));
            return;
        }

        //현재 자리 숫자에 해당하는 모든 문자열 탐색
        for(Character c : dic.get(digits.charAt(index))) {
            //현재 자리 +1, 지금까지 구성된 문자열 path 이용 재귀 dfs
            dfs(result, dic, digits, index+1, new StringBuilder(path).append(c));
        }
    }

 

 

- 끝까지 탐색햇으면 최종 결과를 result 변수에 저장하고 리턴한다. 

- 최종 결과는 문자열이 저장된 path가 되며, 결과로 처리한 이후에는 path의 내용이 유지되면 안된다.

- 즉, 결과 변수인 result는 재귀 탐색할때 내용이 계속 유지되어야 최종 결과를 만들어낼 수 있지만 path는 지금까지의 결과를 저장하고 이후에는 사라져야 하는 값이다.  

 

- 따라서 재귀 탐색할 때 매번 new StringBuilder(path)를 사용해 신규 인스턴스로 넘긴다. 

- path 값은 매번 새로운 인스턴스로 전달해서 리턴되면 사라지도록 처리한다. 

 

 

class Solution {
    public void dfs(List<String> result, Map<Character,List<Character>> dic, String digits, int index, StringBuilder path)
    {
        //끝까지 탐색했으면 결과를 저장하고 리턴
        if(path.length() == digits.length()) {
            result.add(String.valueOf(path));
            return;
        }

        //현재 자리 숫자에 해당하는 모든 문자열 탐색
        for(Character c : dic.get(digits.charAt(index))) {
            //현재 자리 +1, 지금까지 구성된 문자열 path 이용 재귀 dfs
            dfs(result, dic, digits, index+1, new StringBuilder(path).append(c));
        }
    }
    public List<String> letterCombinations(String digits) {
        //결과 저장 리스트 선언
        List<String> result = new ArrayList<>();

        //예외 처리
        if(digits.length() == 0)
            return result;

        //번호로 조합 가능한 문자 목록 구성
        Map<Character, List<Character>> dic = new HashMap<>();
        dic.put('0',List.of());
        dic.put('1',List.of());
        dic.put('2',List.of('a','b','c'));
        dic.put('3',List.of('d','e','f'));
        dic.put('4',List.of('g','h','i'));
        dic.put('5',List.of('j','k','l'));
        dic.put('6',List.of('m','n','o'));
        dic.put('7',List.of('p','q','r','s'));
        dic.put('8',List.of('t','u','v'));
        dic.put('9',List.of('w','x','y','z'));

        //현재 자리 0, 빈 문자열 이용 dfs 시작
        dfs(result, dic, digits, 0, new StringBuilder());
        return result;
    }
}

 

1밀리초