[프로그래머스] 전화번호 목록 Python (Level 2)

TITLE

문제주소 :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 이하입니다.

 

<풀이법>

▒ 한줄 개념: 정렬 후 비교 ▒ 

간단한 문제입니다. 전화번호부 배열 내에 [119, 119155] 처럼 한 전화번호가 다른 전화번호가 접두어가 되는 쌍이 존재할 경우 false를 리턴하고, 존재하지 않으면 true를 리턴하면 됩니다. 

일일히 비교하게 되면 이중반복문이 필요할 것이므로, O(n^2)의 시간 복잡도가 소요될 것입니다.

다만 한번 정렬을 진행하게 되면 [119, O, O, O, 119155...] 처럼 무작위로 흩어져 있던 전화번호들이 [119, 119155, O, O, ...] 처럼 연속해서 위치하게 됩니다.

따라서 반복문을 원소의 갯수만큼 한번만 진행하면 되므로, O(nlogn)+O(n) = O(nlogn)의 시간복잡도를 갖게 되어 더욱 효율적으로 문제를 해결하게됩니다.

 

<코드>

def solution(phone_book):
    answer = True # 디폴트 True
    phone_book.sort() # 정렬을 통해 연속된 인덱스만 비교
    for i in range(len(phone_book)-1): # 반복문을 통해 비교
        if phone_book[i] in phone_book[i+1]: # 접두어가 되는 번호가 있으면,
            answer = False # False
    return answer

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest