[Programmers]] [Python] 전화번호 목록

전화번호 목록

---

문제 설명

---

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

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

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

제한 사항

---

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예

---

['119', '97674223', '1195524421'] | false

['123','456','780'] | true

['12','123','1235','567','88'] false

제출 코드

---

1차 제출 코드

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

    return answer

모든 테스트 케이스는 만족했으나 효율성에서 실패했다.

이중 반복문 내에서 모든 결과값에 대한 비교연산을 진행하니 좀 비효율적이라고 생각은 했다.

어떻게해야 보다 효율적으로 풀 수 있을지 고민을 해보았다.

비교를 진행하는 케이스를 줄이기 위한 방법을 고민하다보니 정렬에서 힌트를 얻었다.

['119', '97674223', '1195524421'] 기존 리스트가 정렬 이후에는 ['119', '1195524421', '97674223'] 으로 정렬된다.

즉, 문자열의 길이가 아니라 시작하는 문자가 정렬의 key가 된다.

따라서, 우리는 지금 접두어만 비교하면 되기 때문에 정렬 이후 앞뒤로만 비교를 진행해주면 된다.

최종 제출 코드

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book) - 1):
        if phone_book[i] in phone_book[i+1]:
            return = False

    return True

코드 설명

우선 리스트를 정렬한다.
다음 각각의 원소들을 순회하며 자기 자신의 옆에 있는 원소와 비교를 진행하되, in 키워드를 통해 문자열 포함여부를 통해 비교한다.

만일 존재할 경우에는 answer를 False를 반환하고 그 외에는 True를 반환한다.

다른 사람의 풀이

---

1) zip() 메서드 이용

phone_book = ['123', '456', '789'] # phone_book[1:] = ['456', '789']

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

동일한 자로형을 zip() 메서드로 묶어 동시에 살펴본다.

접두어 확인을 위해 startswith() 메서드를 사용하였다.

처음 보는 메서드지만 역시 파이썬은 없는게 없다.

2) 정규표현식 이용

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

정규표현식도 매우 깔끔하게 풀이가 가능하다.
컴파일을 통해 표현식을 잡아내고 매치를 통해 접두어를 찾아낸다.

정규표현식에 대해 공부를 해놓으면 두고두고 쓸 것 같다.