6. 전화번호 목록 ★★ (hash table, startswith)

유형 : 해시

구현 시간: 30분 -> 인터넷 검색

 

<나의 풀이>

1. 이중 루프

def solution(phone_book):
    for i in range(len(phone_book)):
        for j in range(i+1, len(phone_book)):
            if phone_book[i] in phone_book[j] or phone_book[j] in phone_book[i]:
                return False
    return True

 

i로 순회하면서 i 이후부터의 아이들과 대조하도록 하였다. 

(당연히) 시간 초과. 

 

2. key 찾기 

def solution(phone_book):
    lenlist = [[x, len(x)] for x in phone_book]
    lenlist.sort(key = lambda x : x[1])
    plist = [x[0] for x in lenlist]
    
    # 길이가 가장 짧은 key를 찾는다. 
    key = plist[0]
    klen = len(plist[0])
    keylist = [key]
    keycount = 1
    for j in range(1, len(plist)):
        if len(plist[j]) > klen:
            break
        else:
            if plist[j] in keylist:
                return False
            keylist.append(plist[j])
            keycount += 1
    #답을 찾는다. 
    for key in keylist:
        for j in range(keycount, len(plist)):
            if key == plist[j][:klen]:
                print(key)
                return False
    return True

 

이중 루프가 문제라고 생각해, 순회횟수를 줄이기 위해 다른 방법을 썼다.

길이가 가장 짧은 아이가 key라고 생각하고 이를 제외한 다른 아이들과 비교하여 답을 찾도록 하였다.

그러나 다양한 문제점이 발생했다. 

1) 길이가 가장 짧은 문자열의 개수가 여러 개인 경우, key가 여러 개이다. 

2) 답이 실패인 test case가 있다..

3) 여전히 시간 초과가 발생

 

 

<정답 >

1. 정렬 이용

정렬을 이용, 사전 순으로 낱말을 배치하면

같은 문자열로 시작하는 문자의 경우 반드시 연달아 배치되게 된다.

따라서 i번째 문자열과 i+1번째 문자열을 비교하면 답을 찾을 수 있다. 

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

 

 

2. Hash Table 이용

def solution(phone_book):
    hashtable = dict([[phone, 1] for phone in phone_book])
    for phone in phone_book:
        acc = ''
        for i in phone:
            acc += i
            if acc in hashtable and acc != phone:
                return False
    return True

 

dict를 사용해 빠르게 문자열을 찾을 수 있는 hash table을 만든다.

phone을 순회하며, 문자열의 문자를 하나씩 append하고, hash table에 존재하는지 check한다.

만약 존재하며, 문자열 자기 자신이 아니라면 False를 return.

중간에 return되지 않고 순회가 종료되는 경우 True를 return. 

 

3. startswith() 함수 사용

이 함수를 사용하면, 접두사인지를 바로 판별할 수 있다. 

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

 

https://mainkey.tistory.com/20