[프로그래머스] LV.2 전화번호 목록(python)

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

프로그래머스

 

문제 설명

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

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

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

제한 사항

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

문제 해결

def solution(phone_book):
    phone_book.sort()
    
    for i in range(len(phone_book)-1): # -1을 하지않으면 list index 초과 발생
        tmp = phone_book[i+1][:len(phone_book[i])]
        if tmp == phone_book[i]:
            return False
    return True

tmp 변수에 다음 인자인 phone_book[i + 1]을 넣고 슬라이싱한다.

다만 접두사인지만 파악하면 되기 때문에 슬라이싱은 현재 phone_book[i]의 길이만큼만 슬라이싱하고

tmp와 phone_book[i]의 값을 비교해 같다면 False, 다르다면 다음 인자로 넘어갈 수 있게 진행했다.

문제 풀이 설명

1. 첫 번째 풀이

def solution(phone_book):
    dic = {i:len(i) for i in phone_book}
    dic = (dict(sorted(dic.items(), key=lambda x:x[1]))) # 길이가 짧은 순부터 검사하기
    for k, v in dic.items():
        for i in phone_book:
            if i == k:
                continue
            c = i[:v]
            if k == c:
                return False
    return True

=> phone_book을 dictionary로 만든다. key는 "phone_book 인자", value는 "각 인자의 길이"로 생성한 후

조건이 충족되면 바로 False를 return, 다 검사할 때까지 없다면 True를 return했다.

하지만 효율성 테스트 3,4 두개가 시간초과가 뜨면서 실패했다,,

 

왜 시간초과가 뜨는지 생각해 본 결과 phone_book에 있는 변수를 길이가 짧은 것부터 비교하는게 의미가 없었다.

단순히 짧은 걸 긴 변수의 접두사와 비교하는게 효율적이라고 생각했지만

사실 인자들은 다 숫자이고, 시작하는 숫자가 같지 않으면 애초에 접두사일 수 없으므로 효율적이지 않다는 결론이 나왔다.

따라서 정렬하는 걸 길이가 아닌  "숫자"를 정렬했다.

쉽게 말해 ["12","88", "567",  "123", "1235"] 을 

["12", "123", "1235", "567", "88"] 로 길이가 아닌 숫자로 정렬했고 초반 "12"를 시작으로 다음 변수의 길이와 같다면 바로

return할 수 있게 했다.