[릿코드] 17 Letter Combinations of a Phone Number (21.05.23)

 

 

 

오늘은

 

기출문제를 푸는 날로

 

 

요즘 유행인 릿코드!!!! 를 사용해보기로 했다!!!!

 

 

 

 

릿코드는 프로그래머스나 백준 같은 알고리즘 사이트로

 

영어로 되어 있는 것과 직접 코드를 작성하면서 확인이 바로 가능하다는 점!!!!!

 

 

 

릿코드 사이트 : https://leetcode.com/problemset/all/

Problems - LeetCode

 

 

 

 

 

---

 

 

 

그래서

 

오늘의 문제는

 

 

바로 바로

 

 

 

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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

 

A phone number picture

 

 

 

문제 사이트 : https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Letter Combinations of a Phone Number - LeetCode

 

 

 

 

---

 

여기서 핵심 포인트!!!

 

 

 

- 어떤 방법으로 letter를 저장할 것인가

 

- 어떻게 번호 조합을 할 것인가

 

- 백트래킹 혹은 재귀 함수 사용!

 

---

 

 

 

 

 

직접 작성해본 소스코드 및 간단한 설명

 

class Solution {
    HashMap<Integer,String> phoneNum = new HashMap<Integer,String>(){{
        put(2,"abc");
        put(3,"def");
        put(4,"ghi");
        put(5, "jkl");
        put(6, "mno");
        put(7, "pqrs");
        put(8, "tuv");
        put(9, "wxyz");
    }};
    
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<String>();
        
        if(digits.length() != 0){
            calculation(result, digits, 0, "");
        }
        return result;
    }
    
    private void calculation(List<String> result, String digits, int i, String resultString){
        if(i == digits.length()){
            result.add(resultString);
            return;
        }
        
        String valueChars = phoneNum.get(digits.charAt(i) - '0');
        for(char c : valueChars.toCharArray()){
            calculation(result, digits, i + 1, resultString + c);
        }
    }
}

 

 

먼저 그림에 있는 번호판과 letter를 매핑시키기 위해

 

• HashMap을 사용했다!!!

 

---

 

굳이 HashMap을 사용하지 않아도 된다!!!

 

그냥 배열에 저장하는 방법도 있다!

 

ex) {"", "", "abc", "def", "ghi", ... }

 

---

 

 

이후에는 어떻게 해결할 것인지 정말 오랫동안 고민했다!!!

 

고민한 결과,,

 

 

 

 

 

digits은 0이상 4이하이기 때문에 반복문을 사용하면 너무 복잡해짐을 느꼈다!

 

그렇기 때문에 사용할 수 있는 방법은 Recursion 밖에 없다고 생각했다!

 

 

 

그렇다면 어떻게 재귀함수로 만들 수 있을까? 무엇을 기준으로?

 

 

 

 

 

 

이 부분에서 DFS 개념이 등장한다!!!

 

하나를 정하면 내가 갈 수 있는 모든 길을 다 탐색해보는 것!!!!

 

 

 

 

이게 우리가 주목해야할 부분이다!!!

 

 

 

 

 

 

• DFS 개념을 사용해서 코드를 작성해보자!!!!

17번에 DFS 개념 넣은 결과 예시

 

 

 

• 그렇다면 무엇을 기준으로 할 것인지 알려줘야 한다!

 

바로 index를 뜻하는 i 이다!!

 

 

 

• 그 다음에는 변화될 값을 정해야한다!

 

계속 더해가면서 변해갈 값이 바로 resultString 이다!!

 

해당 구역의 character를 더해주면서 원하는 값을 만들어간다!!

 

 

 

• 이제 마지막으로 input값과 result값을 넣어주면 끝!!!!

 

 

 

 

 

 

 

 

 

 

 

LeetCode 릿코드

 

SUBMIT 결과 !!!!

 

 

 

ACCEPTED !!!!!!!

 

릿코드 17번 채점 결과

 

 

 

 

 

 

 

 

 

---

스터디하면서 얻은 부분

• DFS/BFS가 개념을 잘 알아야 전혀 다른 부분에서 응용이 가능하다!
• 꼭 HashMap을 하지 않더라도 특성을 잘 파악하면 그냥 Arrray로도 사용 가능하다!

 

 

 

 

 

 

 

 

 

 

 

오늘 처음으로 릿코드 문제를 풀어봤는데

 

 

정말 정말 어렵긴 어렵다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

 

정말 공부를 열심히 해봐야할 것 같다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

 

이번에는 그냥 바로바로 풀었지만, 다음에는 인텔리제이를 사용해서 풀어봐야지 ^_^