[프로그래머스] 전화번호 목록

안녕하세요.

이번 문제는 프로그래머스 2단계 - 전화번호 목록입니다.

 

프로그래머스에서 처음으로 풀어보는 2단계 문제였습니다.

확실히 1단계 문제와는 난이도가 올라간 것이 느껴졌습니다.

설상가상 JS는 지원하지 않는 문제라서.. Python으로 풀이하였습니다.

해당 문제의 경우, 아마도 비교적 최곤에 테스트케이스가 상세하게 추가되고 효율성 검사가 더 어려워졌다고 하더라구요.

 

 그래서 그런지 다 풀고 난 이후에 더 좋은 풀이가 있다면 참고하고자 했으나, 문제 수정 이전에 올라간 정답들이라 효율성 테스트에서 탈락하거나 테스트케이스를 통과하지 못하는 것들이 있더라구요. 이 부분은 조금 아쉬웠습니다.

알고리즘 설명

 이번 문제는 얼핏 보면 중첩 for문을 사용해 쉽게 풀 수 있을 것 같습니다만.. 효율성 부분에서 O(n^2)는 통과하지 못하도록 되어 있더라구요. 그래서 초반에 많이 끙끙거렸고, 정렬을 이용해 풀 수 있을것이라 생각했지만 문제 카테고리가 해시로 잡혀있었던 터라 해시를 통해 풀이하고자 서치를 열심히 해봤습니다. 

 그러던 중 이러한 문자열 검색에 최적화된 자료구조인 Trie 자료구조를 통해 풀 수 있다는 것을 알게 됐고, 해당 알고리즘을 통해 처음엔 열심히 코드를 작성했습니다. 

 

1차 초안입니다. (효율성 1, 3, 4번 통과 실패)

class Node:
    def __init__(self, is_end):
        self.is_end = is_end
        self.hash = {}

class Trie:
    def __init__(self):
        self.nodes = {}
    
    def add(self, word):
        curr = self.nodes
        
        for i in range(len(word)):
            is_last = i + 1 == len(word)
            
            if curr.get(word[i]) is None: 
                curr[word[i]] = Node(is_last)
                
            if is_last == True: 
                curr[word[i]].is_end = True
            else:
                curr = curr[word[i]].hash
                
    def find(self, word):
        curr = self.nodes
        for i in range(len(word)):
            part = word[i]
            
            if curr.get(part) is None: return None
            elif i + 1 == len(word) and curr[part].is_end == True: 
                return curr[part].hash
            else: curr = curr[part].hash
                
        return None
    
    def has_other(self, word):
        result = self.find(word)
        
        if result is not None and len(result.keys()) > 0: return True
        else: return False
            

def solution(phone_book):
    trie = Trie()
    phone_book.sort(key=len)
    
    for phone in phone_book:
        trie.add(phone)
    
    for phone in phone_book:
        if trie.has_other(phone) == True: return False
    
    return True

트라이 알고리즘을 이용해 정석적으로 풀이했던 초안입니다. 우선적으로 테스트케이스는 모두 통과했지만, 효율성에서 탈락했었습니다.

3번 빼고 전부 실패..

모두 시간을 초과했더라구요. 그래서 끙끙거리며 더 공부한 결과, 추가 과정을 굳이 끝까지 할 필요가 없다는 깨달음을 얻어 열심히 수정하였습니다. 물론 코드는 한층 더 난잡해졌고요.. 하하

 

class Trie:
    def __init__(self):
        self.nodes = {}

    def add_and_catch(self, word):
        curr = self.nodes

        for i in range(len(word)):
            part = word[i]
            is_last = i + 1 == len(word)

            if curr.get(part) is None:
                curr[part] = {}
            elif curr.get("*"):
                return True

            if is_last: 
                curr["*"] = True
            else:
                curr = curr[part]

        return False

    def find(self, word):
        curr = self.nodes

        for i in range(len(word)):
            part = word[i]
            is_last = i + 1 == len(word)

            if is_last is True and len(curr[part].keys()) > 0:
                return True
            else:
                curr = curr[part]

        return False

def solution(phone_book):
    trie = Trie()

    for phone in phone_book:
        if trie.add_and_catch(phone) == True: 
            return False

    for phone in phone_book:
        if trie.find(phone) == True: 
            return False

    return True

이 코드로 드디어 통과할 수 있었습니다. 리팩토링을 한번 더 거쳐야 더 직관적인 코드가 될 것 같습니다. 

이번 문제에선 트라이 자료구조를 배울 수 있어 뿌듯했습니다.

 

---

피드백은 언제나 환영이니 부탁드립니다.

읽어주셔서 감사합니다.