[Programmers / Python / 해시] - 전화번호 목록

출처 https://programmers.co.kr/learn/courses/30/lessons/42577

코드를 작성할 때 꼭 써야하는 경우가 아니라면 되도록 중첩 반복문은 잘 안쓰려 하는 편이다.
하지만 제일 먼저 떠오르는 아이디어가 이거 뿐이라 효율성 테스트에서 떨어질 거 같지만 일단 제출해보았다.

# 전화번호부에 적힌 전화번호를 담은 배열 phone_book 

# 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false
# 그렇지 않으면 true를 return 하도록 solution 함수

def solution(phone_book):
    answer = True
    
    for i in phone_book:
        for j in phone_book:
            if (j[0:len(i)]==i) and (j != i):
                answer = False  
            
    return answer

정확성 테스트는 다 맞았지만 역시 효율성 테스트에서 0점을 받았다.

return 을 answer 변수를 사용하지 않고 if 문 true 시 바로 return false
아닌 경우 return true 로 작성해 반복문 실행 횟수를 줄여봤지만 근본적인 해결은 아니라 그런지 여전히 실패가 떴다.

문제에 나온 입출력 예제를 다시 읽어보았고 list 원소의 type이 int가 아니라 str이니 이를 정렬해보면 좋겠다는 생각을 하게 되었다.

list = ["12", "13", "123"]
list.sort()
print(list) #['12', '123', '13']

위와 같이 list가 있을 때 만약 원소의 type이 숫자형이라면 list.sort() 시 ["12", "13", "123"] 의 순서가 되겠지만 type이 str이므로 숫자의 문자열 비교로 정렬이 되어 ['12', '123', '13'] 순이 된다.
그래서 이렇게 정렬 후 앞 뒤 원소만 비교해주면 한 번호가 다른 번호의 접두어인 경우가 있는지 알 수 있다 생각하였다.

문자열에서 특정 문자가 들어있는지 찾기 위해 find를 이용하려 했는데 찾아봤더니 startswith를 이용해 특정 str으로 시작하는지 알 수 있다는 것을 알게 되었다.

def solution(phone_book):
    answer = True

    phone_book.sort()

    for zip1, zip2 in zip(phone_book, phone_book[1:]):
      if zip2.startswith(zip1):
        answer = False

    return answer

phone_book.sort() 해준 뒤에는 앞 뒤 원소만 비교해주면 되기 때문에 zip()에 phone_book와 phone_book[1:] 을 넣어주고 for문을 이용해 각 원소끼리 startswith로 판단했다.

다른 사람의 풀이

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

해시 topic에 있는 문제라 해시로 해결하는 풀이를 찾아봤다.

정리

strA.startswith(strB, 시작 지점)
strA가 strB로 시작하는지 True False 반환
인수로 시작 지점을 지정해줄수도 있다.