[Python - Lv.2] 전화번호 목록

문제

프로그래머스

문제

문제

문제 이해

• 한 번호가 다른 번호의 접두어인 경우가 있는지 확인
• 전화번호를 담은 배열 phone_book
• 어떤 번호가 다른 번호의 접두어인 경우 False, 그렇지 않다면 True 반환

풀이

배열 phone_book을 모두 확인하여 접두어가 있으면 False, 접두어가 없다면 True 반환
배열 phone_book의 길이는 최대 1,000,000이므로 시간 초과에 유의
=> 연산 횟수를 줄이기 위해 배열과 문자열의 길이를 변수를 통해 저장 및 조건문 추가

1. sort 메소드를 통해 phone_book을 정렬 -> (ex. [1, 12, 123, 2, 21, 345, 413])
2. phone_book을 이차 반복문을 통해 하나씩 비교
3. 두 가지 조건을 통해 연산 횟수를 줄이고 오류 발생 방지
4. 중간에 다른 번호에 접두어가 있을 경우 바로 False 반환, 모든 경우에 접두어가 없다면 True 반환

<오류 발생 방지>
접두어인지 확인하기 위해 phone_book[i] == phone_book[j][:l2] 조건을 활용(단, l2 = len(phone_book[i])
만약 phone_book[j]의 길이가 더 짧다면 인덱싱 오류가 발생하므로 해당 조건이 필요

<연산 횟수를 줄이기 위한 조건>
첫 번째 작업으로 phone_book을 사전식으로 정렬
만약 앞에 있는 번호의 크기보다 뒤에 있는 번호의 크기가 크다면 그 이후는 접두어가 존재하지 않음
따라서 int(phone_book[i]) < int(phone_book[j][:l2] 조건을 통해 연산 횟수를 획기적으로 감소

코드

처음에  int(phone_book[i]) < int(phone_book[j][:l2] 조건을 넣지 않고 제출했을 때, 효율성 테스트에서 시간초과가 발생하였다. 따라서 해당 조건을 추가하면 phone_book의 길이가 길어지더라도 빠른 속도로 처리가 가능하다. 실제로 정확성 테스트에서 조건 추가 전에는 791ms가 걸렸던 테스트가 조건 추가 시 3ms로 처리됐다.

def solution(phone_book):
    l = len(phone_book)
    
    phone_book.sort()
    for i in range(l):
        l2 = len(phone_book[i])
        for j in range(i + 1, l):
            if l2 > len(phone_book[j]):
                continue
            elif int(phone_book[i]) < int(phone_book[j][:l2]):
                break
            elif phone_book[i] == phone_book[j][:l2]:
                return False
    return True