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

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

1) 1차 코드

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

정확성 테스트에서 8,9,19 실패
효율성 테스트에서 3,4 실패
정확성이 다 맞더라도 phone_book의 최대 길이가 1e6이기 때문에 이중 for문은 불가능할 것

2) 2차 코드

def solution(phone_book):
    book = {}
    for p in phone_book:
        if len(p) in book:
            book[len(p)].append(p)
        else:
            book[len(p)] = [p]
            
    for p in phone_book:
        for i in range(len(p)-1):
            if i+1 in book.keys():
                if p[:i+1] in book[i+1]:
                    return False
            
    return True

처음에는 번호의 길이별로 dict를 만들어준다
각 번호의 처음부터 끝까지 자릿수를 하나씩 늘려가면서 해당 길이의 번호가 있고, 번호가 동일한 값이 있는지 확인해준다
정확성 테스트는 다 통과했는데, 효율성 테스트에서 4 실패

3) 3차 코드

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

결국 다른 분들의 코드를 몇몇 참고하였다
phone_book을 sorting 해준 후, 앞의 번호가 뒤의 번호의 접두사인지 확인해준다
앞 번호의 길이를 알 필요도 없고, str.startswith() 함수를 사용하면 된다
startswith 함수를 알고 있었음에도 불구하고 코딩을 하려고 하면 떠오르질 않는다
많이 연습해야겠다

추가적인 답안 코드

이 부분은 해당 사이트를 참고했습니다

1) 해시 사용

def solution(phone_book): 

    # 1.Hash map생성
    hash_map = {} 
    for nums in phone_book: 
        hash_map[nums] = 1 
    
    # 2.접두어가 Hash map에 존재하는지 찾기 
    for nums in phone_book: 
        arr = "" 
        for num in nums: 
            arr += num
    
            # 3. 본인 자체일 경우는 제외
            if arr in hash_map and arr != nums:       
                return False 
                
    return True

2) zip, startswith 사용

def solution(phone_book):
    phone_book.sort()

    for p1, p2 in zip(phone_book, phone_book[1:]):
        if p2.startswith(p1):
            return False
    return True

zip을 활용하여 본인과 본인 다음값을 가져온다