#5 전화번호 목록:

date posted: 2020-04-15

오늘의 TMI

1. 아까 씀.

코딩 풀이 시작

이번문제도 hash 를 사용하는 문제입니다.

이전 hash 문제에 사용했던 python hash function 은 프로그램이 다시 시작되면 같은 숫자나 문자를 주어도 다른 hash 값을 생성합니다. hash("leo") = 657454 이였다가 다시 프로그램 껏다키고 돌리면 hash("leo") = 12312 이렇게 됨.

#1 시도

• 4문제 빼고 통과 + 효율성 모두 통과.

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

• 제가 접두사의 뜻을 잘 몰랐음. 무조건 다른 번호 안에 있어도 되는것이아니라 앞자리에 있어야 합니다 (물론 다 아시겠지만).

#2 시도

• check_number 의 길이를 재고 다른 번호들이랑 비교시 [:check_number길이]랑 동일한지 확인
• check_number 가 다른번호의 앞자리에 위치하는지 보기때문에 문제없는거 같은데 2개 실패...흠....

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

• 만약 접두사인 번호가 나중에 나올경우 위 코드는 True 를 줍니다. ["11932", "119", "1345"] 일경우 앞만보고 달리기때문에 "11932" 가 "119" 의 접두사가 될수 없기에 어? 없네 하고 지나쳐버림.
• 그치만 "119" 는 "11932" 의 접두사이기때문에 사실상 False 를 줘야함.
• 앞만 보고 달리지 말고 뒤에도 봐줘보자.

#3 시도

• 뒤도 보니까 모두 성공.
• 하지만 loop 안에 loop 이 있기에 O(n) = n^2 입니다...

def solution(phone_book):
    answer = True
    
    for i in range(len(phone_book)):
        check_number = phone_book[i]
        num_length   = len(check_number)
        for j in range(len(phone_book)):
            if i == j: continue
            if check_number == phone_book[j][:num_length]:
                return False
    return answer

• Hash data structure 를 사용하여 효율을 높여보자.

#4 시도 (Hash 사용)

• 해시 사용해서 풀방법을 못찾음
• 다른사람 풀이들중 해시 사용을 하나 찾음.
• 효율성이 더 떨어지는 해시구현ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
• 조금더 연습후에 완료 하러 다시 오겠음.