[문제풀이] Leetcode 17. Letter Combinations of a Phone Number 자바 풀이

👉 문제

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

입출력 예시:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Input: digits = ""
Output: []

Input: digits = "2"
Output: ["a","b","c"]

✨ 풀이 (미완성)

import java.util.LinkedList;
import java.util.List;

public class LetterCombinationsPhoneNum  {
        public static void main(String[] args)  throws Exception {

            System.out.println(letterCombinations("23"));
            //[ad, ae, af, bd, be, bf, cd, ce, cf]
            System.out.println(letterCombinations("9"));
            //[w, x, y, z]
            System.out.println(letterCombinations(""));
            //[]
            System.out.println(letterCombinations("50"));
            //[[j , k , l ]]
            System.out.println(letterCombinations("11"));
            //[  ]


        }
        public static List<String> letterCombinations(String digits) {
            LinkedList<String> answer = new LinkedList<>();
            answer.add(""); // 널포인터익셉션 해결

            // digits가 빈 경우
            if(digits.length()==0) return answer;

            // 키패드 번호가 알파벳 있는 인덱스와 일치하게 키패드 알파벳 배열 생성
            String[] num = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

            // 반복문으로 answer 채우기
            // 주어지는 digits의 두 수를 for문이 확인할 것
            for(int i = 0; i < digits.length(); i++) {
                // 인덱스 만들어주기
                int j = digits.charAt(i) -'0';

                // 아래 while문 안에 add 메서드를 넣자 널포인터익셉션 에러가 났다. (위로 옮겨서 해결)
                while(answer.peek().length()==i) {
                    String s = answer.remove();
                    for(char c : num[j].toCharArray())
                        answer.add(s+c);
                }
            } return answer;

        }
    }

초기 접근:

모든 번호에 대해 캐릭터 배열을 생성한 후 2중 for문으로 순회하여 리스트 채우기, but 입력받은 숫자와 배열을 매칭해주는 중간 단계에서 막혔고, 풀이의 시간복잡도가 너무 높아질 거라는 결론.

풀이 접근:

• 키패드의 번호와 알파벳을 배열의 인덱스와 스트링으로 매칭시킬 수 있겠다는 생각이 들어 열 칸짜리 배열을 만들어 키패드의 값들을 담았다.
• digit 값 하나마다 문자열을 캐릭터 배열로 쪼개어 알파벳을 가져와, 그것을 앞뒤로 붙여 answer 리스트에 추가해주는 방식으로 반복문을 돌렸다.
• 이 풀이가 미완성인 이유는 키패드의 0과 1 부분을 해결하지 못해서이다. ""을 넣으면 에러가 나서 임시방편으로 띄어쓰기를 한 칸 넣었는데 문제에서 요구하는 답안은 아니다.
• 반복문을 두 번 돌아 효율도 좋지 않다.

개선 아이디어:

• 0과 1에 대한 테스트케이스가 없어서 그런지 submit이 됐고, 위 코드는 속도 및 메모리에서 하위 85%에 속하는 답안이다.
• 효율이 좋은 답들을 보니 별도 메서드를 만들어 StringBuilder로 뜨개질하듯 하나씩 이어붙였다 떼었다 한다. 해시맵을 써서 푼 경우도 더러 있다.
• 현재 풀이에서 개선하고 싶은 점은 시간복잡도와 0, 1에 대한 에러인데 갑자기 따로 메서드를 만드는 것 외에는 방법이 없는지 널포인터익셉션에 대해 다시 살펴봐야겠다..
• 혹시 틀린 부분이 있다거나, 아이디어가 있다면 누구든 댓글 환영합니동🙇🏻‍♀️