[Programmers] level2 - 전화번호 목록 (Python) : 해시

▶전화번호 목록 - 해시 (level 2)

▶문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

▶제한사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

 

▶입출력 예

입출력 예 설명

입출력 예 #1

앞에서 설명한 예와 같습니다.

입출력 예 #2

한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3

첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다.

따라서 답은 false입니다.

▶풀이

풀이를 적다 보니 생각보다 길어져서, 먼저 내 풀이 코드를 올린다.

def solution(phone_book):
    answer = True
    phone_book.sort()
    for a, b in zip(phone_book, phone_book[1:]):
        if b.startswith(a):
            answer = False
            break
    return answer

 

이 문제를 풀다가 zip과 startswith이라는 python함수를 알게 되었다.

zip은 설명하면 각 객체가 담고 있는 원소를 터플의 형태로 차례로 접근할 수 있는 반복자를 반환한다.

간단한 예를 만들어 보았다.

list_a = [1, 2, 3]
list_b = ['a', 'b', 'c']

for l in zip(list_a, list_b):
    print(l)

이 예를 가지고 보면, 두 개 이상의 list에서 같은 인덱스에 해당하는 원소들을 조합하는 것으로 볼 수 있다.

정렬을 한 후에 zip함수를 이용해서 전화번호의 조합을 찾아냈다.

 

["1235", "123", "12348", "012"]을 입력으로 받으면, 정렬하면 ["012", "123", "12348", "1235"]가 된다.

그다음 zip을 해주어서 해당하는 조합을 찾아냈다.

 

설명을 원래 잘 못하기 때문에... 아래 링크를 보면 더 쉽게 이해할 수 있을 거다.

https://www.programiz.com/python-programming/methods/built-in/zip

Python zip()

 

다음으로 사용한 함수는 startswith() 함수이다.

문자열 a, b가 있을 때, b.startswith(a)를 하면 b가 a로 시작한다면 True, 아니면 False를 반환하는 함수이다.

str_a = 'abcdefg'
str_b = 'abc'
str_c = 'xyz'

print(str_a.startswith(str_b))
print(str_a.startswith(str_c))

 

https://www.programiz.com/python-programming/methods/string/startswith

Python String startswith()

zip, startswith 함수를 사용하지 않더라도 정렬 후 조합을 하는 것을 잘 사용한다면, 쉽게 해결할 수 있을 것이다.

사실 나는 그 조합을 제대로 하지 못했는지 효율성 테스트에서 점수를 많이 받지 못했다.

그러다가 zip과 startswith함수를 알게 된 것이다.

아래 코드는 내가 찾아본 다른 사람의 코드이다.

이분은 zip과 startswith을 사용하지 않고 문제를 풀었다.

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