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

chanyeong kim·2021년 12월 31일

hash 프로그래머스

프로그래머스

목록 보기

40/51

vue image

📩 -->문제설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.
- 각 전화번호의 길이는 1 이상 20 이하입니다.
- 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

💡 solution(사용언어: python)

def solution(phone_book):
    phone_book=phone_book
    for i in phone_book:
        for j in phone_book:
            if i!=j and (i.startswith(j) or j.startswith(i)):
                return False
    return True

👉 설명

이중 for문을 이용해서 phone_book에서 문자열을 하나씩 가져오고 가져온 문자열로 시작하는 문자열이 있다면(starts.with을 이용) false를 리턴해주는 방법이었지만 효율성 테스트 3번과 4번을 뚫지 못했다.

💡 Solution 보완

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    return True

아무래도 이중 for문을 사용했기 때문에 보완이 필요했다.
phone_book을 sort를 하면 앞에서부터 작은수를 기준으로 정렬이 되기 때문에 바로 앞뒤에 문자열만 비교를 해주어도 접두사인지 아닌지 구분할 수 있었다.

다른 풀이 (1)

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}

class Trie:
    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        current_node = self.head

        for char in string:
            if char not in current_node.children:
                current_node.children[char] = Node(char)
            current_node = current_node.children[char]
        current_node.data = string

    def search(self, string):
        current_node = self.head

        for char in string:
            if char in current_node.children:
                current_node = current_node.children[char]
            else:
                return False

        if current_node.data:
            return True
        else:
            return False

    def starts_with(self, prefix):
        current_node = self.head
        words = []

        for p in prefix:
            if p in current_node.children:
                current_node = current_node.children[p]
            else:
                return None

        current_node = [current_node]
        next_node = []
        while True:
            for node in current_node:
                if node.data:
                    words.append(node.data)
                next_node.extend(list(node.children.values()))
            if len(next_node) != 0:
                current_node = next_node
                next_node = []
            else:
                break

        return words
    
def solution(phone_book):
    trie=Trie()
    for i in phone_book:
        trie.insert(i)
    for i in phone_book:
        if len(trie.starts_with(i))>1:
            return False
        else:
            return True

이건 Trie라는 알고리즘을 이용한 코드이다.
어떤 알고리즘인지 추후 따로 알고리즘 카테고리에서 포스팅 할 예정이다..
간단하게 노드와 자식 노드를 만들면서 문자를 저장하고 해당 문자열을 검색할 수 있는 알고리즘이다.
근데 위에꺼로 하면 통과 못함... 수정해주어야 하는데, 그냥 Trie를 Class로 만들어본 거 아까워서 가져와 봤다!

다른 풀이 (2)

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer