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

문제

해당 문제 링크

풀이

def solution(phone_book):
    answer = True
    
    h=dict()
    for i in phone_book:
        h[i] =1 #key는 phone_book이고 value는 1로
        
    for i in phone_book: #i는 119, ...
        s=""
        for j in i: #119일 경우 j는 '1', '1', '9' 순으로
            s+=j #+라는게 문자가 이어지는 것
            if s in h and s!=i: #s in h는 접두사 확인하는 것 / s!=i는 똑같은 119 119의 경우는 제외하기 위해
                answer=False
    return answer

결과

다른 사람 코드

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

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

zip()
여러 개의 순회 가능한(iterable) 객체를 인자로 받고, 각 객체가 담고 있는 원소를 튜플의 형태로 차례로 접근할 수 있는 반복자(iterator)를 반환

>> numbers = [1, 2, 3]
>> letters = ["A", "B", "C"]
>> for pair in zip(numbers, letters):
...     print(pair)
>> for i in range(3):
...     pair = (numbers[i], letters[i])
...     print(pair)
...
(1, 'A')
(2, 'B')
(3, 'C')

참고 사이트

해석

처음 작성한 코드는 아래와 같다. 이때 phone_book 가장 앞에 나오는 문장이 기준이 되어 접두어인 경우를 확인하는 줄 알았지만 아니었다. 그렇기 때문에 for문에서 1부터 시작하게 지정하는 것은 잘못된 것이다!

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

이후, 이중 for문을 통해 해결하고자 했지만, 시간 초과라는 결과를 얻었다. 즉, 해시를 이용해서 풀어야 한다는 것이다.
이 문제를 풀면서 startswith()이라는 함수를 알게되었다.

def solution(phone_book):
    answer = True
    
    pb_len=len(phone_book[0])
    
    for i in range(0,len(phone_book)):
        for j in range(i+1, len(phone_book)):
            if(phone_book[i][:pb_len].startswith(phone_book[j][:pb_len])) :
                answer=False
                break
        
    return answer

startswith()
1. 문자열이 특정 문자열로 시작하는지 확인

str = 'Hello world, Python!'
if str.startswith('Hello'):
    print('It starts with Hello')
if not str.startswith('Python'):
    print('It does not start with Python')
###OUTPUT###
It starts with Hello
It does not start with Python

대소문자를 구분하지 않으려면 lower()로 소문자로 변경 후, 소문자로 비교 가능

str = 'Hello world, Python!'
if str.lower().startswith('hello'):
    print('It starts with hello')
###OUTPUT###
It starts with hello

2. split()으로 단어가 특정 문자열로 시작하는지 확인

str = 'Hello world, Python!'
strings = str.split()
list = []
for word in strings:
    if word.startswith('Python'):
        list.append(word)
print(list)
###OUTPUT###
['Python!']

3. Comprehension과 startswith()로 단어가 특정 문자열로 시작하는지 확인

list = [word for word in strings if word.startswith('Python')]
print(list)