전화번호 목록

전화번호 목록

 

# 전화번호 목록

# 링크 : https://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 이하입니다.

# 같은 전화번호가 중복해서 들어있지 않습니다.

# 입출력 예제

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

 

# 입출력 예 설명

# 입출력 예 #1

# 앞에서 설명한 예와 같습니다.

# 입출력 예 #2

# 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

# 입출력 예 #3

# 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

# 알림

# 2021년 3월 4일, 테스트 케이스가 변경되었습니다. 이로 인해 이전에 통과하던 코드가 더 이상 통과하지 않을 수 있습니다.

---

소스

# ----------------- 시도 -----------------------
# 1
def solution1(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        for j in range(i+1, len(phone_book)):
            if phone_book[j].startswith(phone_book[i]): 
                return False
    return True
# 정확성: 83.3
# 효율성: 8.3
# 합계: 91.7 / 100.0

# ----------------- 통과 -----------------------
# 2  짧은것으로 긴것을 검사
def solution2(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].startswith(phone_book[i]): 
                return False
    return True
# ----------------- 다른 답안 -----------------------
# 3 긴것으로 짧은것을 검사
def solution3(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

# 4 정규식활용 - 효율성 좋지 않음
import re
def solution4(phoneBook):

    for b in phoneBook:
        p = re.compile("^"+b)
        for b2 in phoneBook:
            if b != b2 and p.match(b2):
                return False
    return True
# 채점 결과
# 정확성: 83.3
# 효율성: 8.3
# 합계: 91.7 / 100.0

solution1 같은 경우 리스트를 정렬을 시킨 후 2중 반복문을 통해 정렬된 리스트들을 startswith()라는 내장 함수로 검사를 합니다. startswith() 함수는 괄호 안의 문자열로 시작하는 문자열인지 검사해주는 함수입니다. 이렇게 할 경우 시간 복잡도가 O(n^2)이 되기 때문에 효율성이 떨어집니다.

 

solution2 같은 경우 1번 풀이와 똑같이 리스트를 정렬을 시키지만 1개 반복문을 통해 값을 받아 냅니다. 그이유는 sort()를 할 경우 key값을 주지 않은 경우 오름차순 정렬이 되기 때문에 해당 인덱스와 그다음 인덱스만 검사만 하면 됩니다.  여기서 검사를 할 때도 if문을 통해 각 값의 길이를 검사하게 될 경우 쓸데없이 startswith()를 할 수고를 덜어줘 상대적으로 복잡도가 줄어듭니다.

 

solution3같은 지금까지 와의 풀이와는 다르게 따로 정렬을 하지 않고 긴 것에서 짧은 것을 검사합니다. 처음에는 반복문을 통해 전화번호 딕셔너리를 만들어줍니다. 리스트 대신 딕셔너리를 사용하는 이유는 딕션너리가 in을 사용하는데 특화되어있기 때문입니다. 이렇게 각각의 번호를 키값으로 딕셔너리를 만들고 그다음 에는 2중 for문을 사용하여 temp라는 변수에 글자를 하나씩 넣어 이 값과 일치하는 key가 딕셔너리에 존재하는지 그리고 temp값 최대치가 되지 않았는지 검사를 하게 됩니다. 긴 것에서 짧은 것을 검사한다는 이유도 짧은 것을 아무리 검사해도 일치하는 값이 존재하지 않다고 나오기 때문입니다. 이문제에서도 시간 복잡도가 O(N^2)처럼 보이지만 전화번호 길이에 제한이 20자 제한이므로 O(N)이 됩니다.

 

https://coincidence24.tistory.com/entry/12-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B8%B0%EC%B4%88-%EA%B0%95%EC%9D%98-%EB%94%95%EC%85%94%EB%84%88%EB%A6%ACdictionary-%ED%82%A4key-%EA%B0%92value-%ED%99%95%EC%9D%B8-%EB%94%95%EC%85%94%EB%84%88%EB%A6%AC%EC%99%80-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%EC%B0%A8%EC%9D%B4%EC%A0%90-get%ED%95%A8%EC%88%98-keys%ED%95%A8%EC%88%98-values%ED%95%A8%EC%88%98-items%ED%95%A8%EC%88%98

[#12 파이썬 기초] 딕셔너리(dictionary) 키/값 확인, 딕셔너리와 리스트 차이점, get()함수, keys()함수,

 

solution4같으겨우 re모듈의 compile() 함수와 정규식을 할 용 하여 결과값을 뽑는 방법입니다. 이렇게 할 경우 효율성이 좋지 않기 때문에 이 방법보다는 이전에 소개한 방법을 쓰는 것이 좋습니다

https://docs.python.org/ko/3/howto/regex.html

정규식 HOWTO — Python 3.10.2 문서