📖 문제

📝 풀이 과정

1. 리스트 phone_book을 정렬한다.
   왜냐하면 앞글자들이 같아야지만 접두어가 될 가능성이 높은데, 정렬을 해야 앞글자가 비슷한 것끼리 모인다.
2. 새로운 딕셔너리에 값을 넣는다.
   key는 전화번호의 첫 숫자를, value에는 key를 첫 숫자로 가지는 전화번호 리스트를 담는다.
   • 딕셔너리 예시)
     
3. data의 key별로 values를 순회한다.
   순회하면서 앞에 있는 수가 뒤에 있는 수들의 접두어가 될 수 있는지 확인한다.
   -> 이게 가능한 이유는 리스트 phone_book이 정렬되어 있어서 딕셔너리 data의 values에 들어가는 값들도 정렬되어있음을 보장하기 때문이다.

그리고 코드는 좀 지저분해지지만.. answer가 False임에도 불구하고 남은 for문을 다 돌아가는 것을 방지하기 위해서

if answer == False :
    break

을 좀 남발했다.... 이렇게 해도 효율성 테스트 3번과 4번은 통과하지 않았지만 이 코드마저 없었다면 효율성 테스트 1번과 2번도 통과하지 못하는 것을 확인했다.

⌨ 코드(틀린 코드)

-> 정확성 테스트는 모두 통과했지만, 효율성 테스트3,4는 통과하지 못한 코드입니다.

def solution(phone_book):
    answer = True
    data = dict()
    
    # 1. 리스트 phone_book을 정렬한다.
    phone_book.sort()
    # 2. 새로운 딕셔너리에 값을 넣는다.
    for phone_number in phone_book:
        # 이미 딕셔너리에 첫글자가 있다면
        if phone_number[0] in data:
            data[phone_number[0]].append(phone_number)
        else:
            data[phone_number[0]] = [phone_number]
            
    # 3. data의 key별로 values를 순회한다.
    for num in data:
        if answer == False:
            break
        p_numbers = data[num]
        # 앞쪽에 있는 수 -> index i
        for i in range(0,len(p_numbers) - 1):
            if answer == False:
                break
            # 뒤쪽에 있는 수 -> index j
            for j in range(i + 1, len(p_numbers)):
                if p_numbers[i] in p_numbers[j]:
                    answer = False
                    break
    return answer

⌨ 다른 분의 코드 참고 -> 더 효율적인 코드

• phone_book을 정렬한다면 어떤 번호의 접두어가 될 수 있는 코드는 서로 인접하게 된다. 따라서 앞뒤 번호끼리만 비교해주면 정답을 구할 수 있다.
• 하지만 해시 자료형은 쓰지 않는다.

def solution(phone_book):
    answer = True

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

⌨ 다른 분의 코드 -> 해시맵을 사용한 코드

• 해시맵에 phone_book에 있는 전화번호를 모두 key값으로 저장한다. 이때 value는 의미없는 값이다.
• phone_book에 있는 전화번호를 한글자씩 가져와 temp 변수에 붙여가면서 현재까지 구한 temp가 해시맵에 존재하는지 검사한다.

def solution(phone_book):
    answer = True
    hash_map = {}
    
    # 해시맵에 phone_book에 있는 전화번호를 모두 key값으로 저장한다.
    for phone_number in phone_book:
        hash_map[phone_number] = 1
        
    # phone_book에 있는 전화번호를
    for phone_number in phone_book:
        temp = ""
        # 한글자씩 가져와 
        for number in phone_number:
            # temp 변수에 붙여가면서
            temp += number
            # 현재까지 구한 temp가 해시맵에 존재하는지 검사한다.
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer