[프로그래머스] 전화번호 목록 Python

문제 보기

🔒 문제

🔐 해결 과정

1. 전화번호부를 오름차순 정렬한다.
2. 앞번호와 뒷번호의 길이를 비교한 뒤, 긴 번호의 맨 앞에 작은 번호가 포함되어 있는지 확인한다.

🔓 풀이 (50m)

2022.04.22

1차 시도

def solution(phone_book):
    idx = 0
    length = len(phone_book)
    while idx < length-1:
        for i in range(idx+1, length):
            if(phone_book[i].find(phone_book[idx]) == 0): return False
        idx+=1
    return True

테스트케이스 8, 9, 19번 실패하고 효율성 3, 4번이 시간초과됐다. 지금 살펴보니 길이비교없이 무작정 뒷번호에 앞번호가 접두어로 들어가 있는지 비교하고 있다는 것을 알았다.

2차 시도

def solution(phone_book):
    idx = 0
    length = len(phone_book)
    while idx < length-1:
        for i in range(idx+1, length):
            if(len(phone_book[idx]) < len(phone_book[i])):
                if(phone_book[i].find(phone_book[idx]) == 0): return False
            else:
                if(phone_book[idx].find(phone_book[i]) == 0) : return False
        idx+=1
    return True

오 내가 생각한게 맞았다. 테스트케이스는 모두 성공하고 이제 효율성 해결만 남았다. 근데 효율성이 안 나올만 한게, 굳이 인덱스를 하나씩 옮겨가며 뒷부분의 모든 전화번호와 비교하고 있다. 이 부분을 개선해야겠다.

3차 시도

def solution(phone_book):
    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].find(phone_book[i]) == 0): return False
        else:
            if(phone_book[i].find(phone_book[i+1]) == 0): return False
    return True

통과했다. 전화번호부를 오름차순 정렬한 뒤 앞뒤 번호 중 길이가 긴 번호 앞에 작은 번호가 맨 앞에 위치하는지 확인했더니 됐다.

🔁 feedback

한 문자열의 0번째 인덱스에 다른 문자열 전체가 들어가 있는지 확인하는 아주 간단한 문제였는데 규칙을 제대로 정리하지 않고 풀어서 오래 걸렸다.

+ 다른 사람의 풀이

✔️ startswith() 사용

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

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

zip()으로 묶어서 코드가 훨씬 깔끔하게 보이고, 접두어를 확인하는 startswith() 함수가 있다는 것을 알게 되었다. (반대는 endswith())

✔️ 해시 사용

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

전화번호를 모두 해시에 키값으로 넣어둔다. (값은 아무거나 상관없다.) 전화번호의 앞에서부터 한자씩 한자씩 꺼내 붙여가면서 해시에 키로 존재하는 것이 있는지 확인한다. 만약에 있으면 접두어가 존재하는 것으로 한다.