LeetCode swift, Letter Combinations of a Phone Number 문제풀이

 

안녕하세요~ 개발자 멍구입니다.
오늘은 LeetCode의 Letter Combinations of a Phone Number 를 풀어보았어요. 바로 보겠습니다!

 

---

릿코드 Letter Combinations of a Phone Number 문제 설명

해당 문제는 2~9의 키패드에 입력가능한 문자가 정의되어있는데요. 특정 digits 가 주어졌을때 해당 digits로 입력 가능한 모든 문자 케이스를 반환하는 문제였습니다. 이때 반환하는 케이스는 문자열 배열 형태로 반환하고, 반환되는 문자열의 순서는 신경 안써도 됩니다.

바로 문제 풀어보겠습니다. 보시기 전에, 안푸셨다면 먼저 릿코드에서 해당 문제를 직접 풀어보시고 보시길 추천드립니다! 

 

---

릿코드 swift 문제 풀이 시작

문제 풀어볼게요. 3행에서는 digits 입력값이 비었을때의 케이스를 미리 필터링해줍니다. 이때에는 입력가능한 문자가 없으므로 빈 배열을 반환합니다.

5~16행) 이어서 2 ~ 9의 키패드로 입력가능한 문자들을 digitToLetters에 정의했어요.

17~19행) 정답을 넣을 res 배열, digits 길이를 digitsLen에 담아두고, Character 배열의 digitArray도 담아놓습니다. 이렇게 미리 담아놓는 이유가 뭘까요?

swift의 String는 일반 배열처럼 간단하게 첨자접근을 하기 어렵습니다. 또한 String 에서 제공하는 인덱스로 접근하는 경우 시간복잡도가 O(N)입니다. 그리고 String count 를 통해 문자열 길이를 반환받을 시에도 시간복잡도가 O(N)입니다. -> 그렇기 때문에 이런 연산이 많아지는 경우에는 미리 해당 결과를 초반에 한번 받아두고 사용하는 것이 더 좋습니다!

 

 

backtract 이라는 메서드를 정의했습니다. DFS로 돌리는 메서드입니다.

21행) backtrack 메서드를 정의합니다. dfs로 활용되며, solution 메서드 내에 중첩 메서드로 정의했습니다. 

22 ~ 25행) "23" 과같은 digits 입력을 받았을때 입력 가능한 문자는 전부 digits 입력 길이와 같은 길이가 됩니다. 따라서 digitsLen과 현재 순회하는 index가 같아지게 될때 (현재 입력된 문자 길이가 digits 길이와 같아지면) 정답으로 쌓아놓습니다.

27 ~30행)
이 다음 체크해야하는 digitNumber를 반환받습니다. Character 타입에서는 swift 5.1 부터 asciiValue 라는 프로퍼티를 제공합니다. '1' Character 의 asciiValue 에서 48을 빼면, 1 이라는 값을 얻을 수 있습니다.

digitNumber로 입력가능한 모든 케이스를 순회하는 모습입니다. 2를 방문한다면, 'a', 'b', 'c'를 추가한 문자열 케이스를 방문하게 됩니다! 그렇게 dfs를 순회하면서 입력가능한 모든 문자열을 res에 쌓게 됩니다. 입력으로 주어진 digits 를 순차적으로 방문하는 케이스이므로 이 이상 복잡한 로직을 필요로 하지 않았어요.

문제풀이 끝, 결과를 보겠습니다.

 

---

LeetCode swift 문제풀이 후 제출 결과

Beats 100.00%가 나오네요. 이번 문제의 핵심은 모든 2~9의 키패드로 입력 가능한 모든 케이스를 dfs 등의 순회로 찾을 수 있느냐가 될 것 같고, 그에 따른 기저조건 (더이상 방문할 필요가 없는 케이스를 필터링) 설정도 중요합니다.

추가로 swift 언어로 풀게 된다면, 유니코드 호환이 가능한 swift 문자열의 원리를 감안하고 count, 첨자접근 방식을 고려해볼 수 있었던 문제였습니다.

 

 

---

해당 문제는 LeetCode study plan에서 풀었습니다. 종종 해당 페이지에 있는 문제를 풀어보려고해요. 지금까지 Letter Combinations of a Phone Number swift 풀이였습니다. 더 좋은 아이디어나 질문이 있다면 언제든 댓글 주세요. 감사합니다~! ☺️