프로그래머스 - 전화번호 목록 [파이썬]

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

코딩테스트 연습 - 전화번호 목록

---

풀이 과정

1. 정렬해서 풀기

처음 풀었을 때는 phone_book.sort(key=lambda x: len(x)) 방법으로 길이순으로 정렬하고 string.find() 명령어를 이용해서 풀었다. len(phone_book)이 4라고 한다면 (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)의 순서쌍에 대해 뒤의 인덱스가 앞의 인덱스의 문자열을 포함하고 있는지를 살펴봤으나 이렇게 풀면 문제를 잘못 읽은 것이다. 특정 전화번호가 다른 전화번호를 포함하고 있는지를 묻지 않았고 다른 전화번호로 시작했는지를 물어봤으니 다른 전화번호를 문자열 중간에 포함하고 있는 경우에 잘못된 답을 출력하게 된다.

 

그리고 위와 같은 순서쌍을 만들어서 비교하는 방법은 2중 for문을 돌려야 하는데 시간복잡도 문제때문에 효율성 테스트 3, 4번을 통과할 수 없다. 예전에는 효율성 테스트 3, 4번 케이스가 없었으므로 2중 for문으로 해결한 코드도 좀 보이는 것 같은데 지금은 for문을 2번 사용해서는 효율성 테스트에서 통과할 수가 없다.

 

파이썬에서 문자열에 대해 sort()를 사용하면 첫번째 문자에 대해 정렬, 첫번째 문자가 같다면 두번째 문자에 대해 정렬... 순으로 이루어진다 아래 예시를 보자

 

a = ['567', '88', '123', '1235', '12']

a.sort()

a = ['12', '123', '1235', '567', '88']

 

예시를 보면 이미 한번 정렬을 했으면 for문을 2번 돌릴 필요가 없다는 것을 알게 된다. 그냥 뒤의 문자열이 앞의 문자열로 시작하는지만 체크해주면 모든 문자열의 접두어 시작 여부를 알 수가 있게 된다.

 

2. 해쉬로 풀기

모든 전화번호를 딕셔너리에 넣은 후, 각 전화번호의 처음부터 일정 부분까지의 부분 문자열을 딕셔너리의 키 값으로 주고 딕셔너리를 조회하면서 각 전화번호의 부분 문자열이 다른 전화번호와 같은지 확인하면서 푸는 방법이 있다.

 

부분 문자열은 문자열과 같아서는 안된다. 그러면 부분 문자열이 문자열과 같아지면 딕셔너리에 항상 존재하게 되고, 한 번호가 다른 번호의 접두어인 경우가 아니더라도 접두어가 존재한다고 판단하게 된다.

 

만약에 처음부터 일정 부분까지의 부분 문자열이 다른 전화번호와 동일하다면 다른 전화번호가 문자열의 접두사가 된다.

---

소스 코드

1번

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

 

2번

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