[프로그래머스 코딩테스트 고득점 Kit / 해시] 전화번호 목록 (python)

+ 2024.06.10 재풀이

풀이: set

def solution(phone_book):
    pb = set(phone_book)
    
    for number in phone_book:
        prefix = ''
        for n in number:
            prefix += n
            if prefix!= number and prefix in pb:
                return False
    return True

 

이전에 해시 알고리즘을 사용하기 위해 딕셔너리로 풀었는데, 다시 생각해보니 안에 전화번호가 있는지만 확인하는 용도로만 쓸거면 굳이 딕셔너리를 사용하기보다는 집합을 사용하는 게 나을 것 같았다.

 

전체 전화번호 리스트를 우선 pb 집합에 넣는다.

그리고 phone_book 리스트 전체를 돌면서 각 번호의 접두어가 pb에 존재하는지 확인한다. 각 번호의 접두어는 prefix 변수에 할당했다.

접두어가 현재 번호와 같지 않을 때(이 조건을 넣지 않으면 pb 안에 해당 번호는 무조건 존재하기 때문에 모든 상황에 False가 리턴됨) 접두어가 pb에 존재한다면 False를 리턴하고, 모든 반복문을 다 돌고나서도 리턴되지 않았으면 접두어가 존재하지 않는다는 의미로 True를 리턴한다.

 

풀이1 : Trie

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

class Trie(object):
    def __init__(self):
        self.head = Node(None)
             
    def insert(self, string):
    	# 헤더부터 가리키면서 내려옴
        curr_node = self.head
        
        for char in string:
            # 자식 노드 만드는 와중에 완성된 글자가 있으면 False 반환
            if curr_node.data != None:
                return False
            # 자식 Node들 중 같은 문자가 없으면 Node 새로 생성
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            # 같은 문자가 있으면 노드를 따로 생성하지 않고, 해당 노드로 이동
            curr_node = curr_node.children[char]
        
        # 마지막 문자를 가리키는 Node 밑에 자식 노드가 있을 경우 False 반환
        if curr_node.children != {}:
            return False
            
        #문자열이 끝난 지점의 노드의 data값에 해당 문자열을 입력
        curr_node.data = string
        return True

        
def solution(phone_book):
    answer = True
    trie = Trie()
    
    for i in phone_book:
        if trie.insert(i) == False:
            answer = False
    
    return answer

내 풀이

- 효율성 테스트 통과x

• 문제를 보고 예전에 자료구조 시간에 들었던 Trie가 생각나서 Trie로 문제 해결 시도
• 트라이에 배열 삽입하는 과정에서 true, false를 판단함. false인 경우는 2가지
  1. 자식 노드를 만드는 와중에 완료된 문자열이 있다면, 그 완료된 문자열이 현재 만들고 있는 문자열의 접두어라는 의미이므로 False 반환
  2. 문자열 저장을 완료했는데 마지막 문자를 가리키는 Node 밑에 자식 노드가 있을 경우, 지금 저장한 문자열이 접두어라는 의미이므로 False 반환

 

풀이 2 : 리스트

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

모범 답안 참고.

배열로 풀면 시간이 더 오래 걸릴 것 같아서 Trie로 풀었는데 그 반대의 결과가 나옴..

• 배열 슬라이싱을 이용해서 문제 해결.
• phone_book을 정렬한 뒤, 배열 전체를 반복문을 통해 돈다. 반복문을 돌면서 자기 뒤에 있는 원소를 자신의 길이까지 슬라이싱하여 내 접두어인지를 확인한다.
• 정렬을 하면, ['9658', '485566', '422', '566', '65824', '99'] 인 경우
  ['422', '485566', '566', '65824', '9658', '99']로 바뀌기 때문에 맨 앞에 시작하는 문자열이 비슷한 것끼리 묶이게 된다. 따라서 접두어를 비교하기 쉬워지기 때문에 정렬을 사용한다.

 

풀이 3 : dictionary

def solution(phone_book):
    answer = True
    
    dict1 = dict.fromkeys(phone_book, 0)

    for i in phone_book:
        arr = ""
        for j in i:
            arr += j
            if arr in dict1 and arr != i:
                answer = False
    
    return answer

모범 답안 참고.

• 딕셔너리를 이용해 문제 해결.
•  dict.fromkeys()를 활용해 value는 0으로 고정하고 phone_book 리스트의 원소를 dictionary의 key 값으로 모두 저장.
• phone_book 리스트는 반복문을 돌고, 배열 안에 각 문자열은 빈 문자열("")에서부터 문자 하나씩 더하면서 이런 접두어가 딕셔너리에 존재하는지 확인. 자기 자신을 제외하고 접두어가 존재한다면 answer에 False 할당.

 

이번 문제는 리스트로 풀었을 때가 딕셔너리보다 빨랐음

 

참고

https://velog.io/@gojaegaebal/210126-%EA%B0%9C%EB%B0%9C%EC%9D%BC%EC%A7%8050%EC%9D%BC%EC%B0%A8-%ED%8A%B8%EB%9D%BC%EC%9D%B4Trie-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EB%B0%8F-%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0feat.-Class python trie