[프로그래머스][LV.2] 전화번호 목록 | python3

문제링크:  전화번호 목록

---

문제설명

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

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

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

 

제한조건

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

---

 

문제풀이

리스트를 돌면서 비교하고, 접두사 인 것이 있으면 False를 리턴한다.

 

def solution(phone_book):
    answer = True
    for i in range(len(phone_book)-1):
        for j in range(i+1,len(phone_book)):
            if phone_book[i] in phone_book[j] or phone_book[j] in phone_book[i]:
                return False
    return answer

 

정확도테스트 1,5,13,14

효율성테스트 3,4 (시간초과)

실패.

 

def solution(phone_book):
    answer = True
    # 이중 for문은 시간이 오래 걸리는 것 같음. 
    # 맨 처음부터 같아야 하니까 sort로 정렬하면 앞뒤로만 비교하면 됨.
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i] in phone_book[i+1]:
            return False
    return answer

13번 틀림... 왜지.. 무슨 조건을 추가해야 하는걸까.

반례 :: [0,10]

앞글자부터 같아야하기때문에 조건에 추가해줬다.

 

나의코드

def solution(phone_book):
    answer = True
    # 이중 for문은 시간이 오래 걸리는 것 같음. 
    # 맨 처음부터 같아야 하니까 sort로 정렬하면 앞뒤로만 비교하면 됨.
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        # [0,10] 의 경우 값이 False가 됨. 앞글자가 같아야한다는 조건 추가
        if phone_book[i][0]==phone_book[i+1][0] and phone_book[i] in phone_book[i+1]:
            return False
    return answer

 

참고하기

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

해시를 이용하여 푼 풀이.

---

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

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

 

---

✅ startswith() 함수란?

사용법:

문자열.startswith(부분문자열)
✅ 주어진 문자열이 특정 문자열로 시작하는지 확인하는 함수.

text = "hello world"

print(text.startswith("hello"))  # True
print(text.startswith("world"))  # False
print(text.startswith("h"))      # True

📌 문자열의 앞부분이 특정 문자열과 일치하는지 검사할 때 유용함!
p2.startswith(p1)는 p2가 p1로 시작하는지 확인하는 코드.

---

🔹 예제 실행

phoneBook = ["119", "97674223", "1195524421"]
print(solution(phoneBook))  # False (119가 1195524421의 접두어)

phoneBook = ["123", "456", "789"]
print(solution(phoneBook))  # True (접두어 없음)

phoneBook = ["12", "123", "1235", "567", "88"]
print(solution(phoneBook))  # False (12가 123의 접두어)

---

🔥 코드의 핵심 아이디어

1. 정렬하면 접두어 관계가 있는 번호들이 인접하게 정렬됨.
2. 앞뒤 번호만 비교하면 되므로 O(N)번만 확인하면 됨.
   → 정렬(O(N log N)) + 한 번씩만 비교(O(N)) → 최적화됨!
3. startswith()를 활용해 접두어 관계를 쉽게 확인.

✔️ 효율적이고 직관적인 코드! 🚀

---

import re
def solution(phoneBook):

    for b in phoneBook:
        p = re.compile("^"+b)
        for b2 in phoneBook:
            if b != b2 and p.match(b2):
                return False
    return True

 

 

🔹 코드 분석

import re  # 1️⃣ 정규 표현식 모듈 불러오기

def solution(phoneBook):
    for b in phoneBook:  # 2️⃣ 각 전화번호(b)를 기준으로 접두어 검사
        p = re.compile("^" + b)  # 3️⃣ 정규 표현식 패턴 생성 (b로 시작하는 문자열 찾기)

        for b2 in phoneBook:  # 4️⃣ 다른 전화번호들과 비교
            if b != b2 and p.match(b2):  # 5️⃣ b가 b2의 접두어이면 False 반환
                return False
    
    return True  # 6️⃣ 접두어 관계가 없으면 True 반환

---

🔹 정규 표현식 (re.compile("^" + b)) 사용법

✔ re.compile(pattern)

• 주어진 정규 표현식 패턴을 컴파일하여, 여러 번 사용할 수 있도록 만듦.

✔ "^" + b

• "^"는 문자열의 시작을 의미함.
  즉, b로 시작하는 문자열을 찾는 패턴을 만듦.

예를 들어, b = "119"일 때:

p = re.compile("^119")  # 119로 시작하는 문자열 찾기

✔ p.match(b2)

• b2가 패턴 p와 일치하는지 검사.
• b2가 b로 시작하면 match()가 True를 반환.

---

🔹 예제 실행 (정규 표현식 매칭 확인)

import re

phoneBook = ["119", "97674223", "1195524421"]

for b in phoneBook:
    p = re.compile("^" + b)  # b로 시작하는 패턴 생성
    for b2 in phoneBook:
        if b != b2 and p.match(b2):  # b가 b2의 접두어인지 확인
            print(f"{b} is a prefix of {b2}")  # 접두어 관계 출력

출력 결과:

119 is a prefix of 1195524421

→ "119"는 "1195524421"의 접두어이므로 False를 반환해야 함.

---

🔥 코드의 핵심 아이디어

1. 정규 표현식 (re.compile("^" + b))을 사용하여 접두어 검사.
2. 모든 전화번호에 대해 다른 번호들과 비교.
   • 같은 번호끼리는 비교하지 않음 (b != b2).
   • b가 b2의 접두어인지 확인 (p.match(b2)).
3. 접두어 관계가 있으면 즉시 False 반환.
4. 모든 비교가 끝나면 True 반환.

---

🚀 코드의 문제점과 개선 방법

❌ 시간 복잡도 문제

이 코드는 **O(N²)**의 시간 복잡도를 가짐.
(각 전화번호에 대해 나머지 전화번호들과 비교해야 하기 때문)

📌 더 효율적인 방법

• 정렬 후 startswith() 사용 (O(N log N))
  → 이전에 설명한 코드 (sorted(phoneBook) 후 startswith() 체크)
• 해시 테이블(딕셔너리) 활용 (O(N))
  → 해시를 이용하면 한 번의 탐색으로 접두어를 찾을 수 있음.

✔️ 정규 표현식 대신 startswith()을 사용하면 속도가 더 빠름! 🚀