[프로그래머스] 전화번호 목록 - Lv.2

프로그래머스 42577번 문제인 "전화번호 목록" Lv.2을 파이썬으로 풀어보도록 하겠습니다.

[프로그래머스] 전화번호 목록 Lv.2 - [파이썬/python]

 

 

프로그래머스-전화번호-목록

---

💻 문제 설명

 

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

 

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

 

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

 

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

프로그래머스

---

🚨 제한사항

 

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

---

 

 

---

---

---

!!!정답 주의!!!

---

---

---

 

 

 

---

🌟 소스 코드

 

프로그래머스-전화번호-목록-파이썬-코드

 

 

 

 

def solution(phone_book):

   

    # 정렬하기 => 접두어가 되는 번호가 항상 인접한 위치에 있음

    phone_book.sort()

   

    # 현재 전화번호와 다음 전화번호를 순차 비교

    # 접두어가 있다면 False 반환

    for i in range(len(phone_book)-1):

        if phone_book[i+1].startswith(phone_book[i]):

            return False

   

    # 접두어가 없다면 True 반환

    return True

 

 

 

 

---

⏱ 시간복잡도

 

위 코드의 시간복잡도는 O(n log n)입니다.

 

 

정렬하기: phone_book.sort()

전화번호를 정렬하는 데는 O(n log n)의 시간이 소요됩니다. 여기서 n은 전화번호의 수입니다.

 

반복문 순회하기: for i in range(len(phone_book)-1):

모든 전화번호를 순회하는 데는 O(n)의 시간이 소요됩니다.

 

문자열 비교하기: if phone_book[i+1].startswith(phone_book[i]):

문자열을 비교하는 데는 O(m)의 시간이 소요됩니다. 여기서 m은 문자열의 길이입니다.

 

따라서, 이 코드는 전화번호를 한 번만 순회하고, 각 전화번호에 대해 상수 시간의 연산을 수행하므로, 전체 시간 복잡도는 O(n log n + n*m)입니다. 그러나 보통 복잡도에서는 가장 큰 항만을 고려하므로, 이 코드의 시간 복잡도는 O(n log n)으로 간주할 수 있습니다. 이는 입력 크기에 대해 로그 선형적으로 비례하는 시간 복잡도를 의미합니다.

 

 

 

---

🏳‍🌈 테스트 결과

 

프로그래머스-전화번호-목록-상태

 

 

프로그래머스-전화번호-목록-테스트-결과