문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 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 |
풀이
- 특정 값(어떤 번호의 접두어에 해당하는 번호)이 자료구조 안에 존재하는 지를 검색(탐색)하는 문제다. 일반적으로 Array를 활용하여 값을 찾는 경우, 첫 번째 인덱스부터 마지막 인덱스를 차례대로 순회해야 하기 떄문에 시간 복잡도가 엄청나게 커지는 문제가 생긴다. 그래서 검색에 높은 성능을 보여주는 해시를 응용하여 문제 풀이에 접근하는 것이 좋다.
-
우선 phone_book의 요소들을 key:value 형태의 자료구조(dict)에 담아주도록 하자. 담는 방법은 크게 두 가지다. 하나는
for loop를 활용해 phone_book의 요소들을 담는 동시에 접두어에 해당하는 번호가 존재하는지를 검색하는 방법이다. 다른 하나는 일단 모든 요소를 담은 뒤에 검색을 시작하는 것이다. 전자는 코드의 가독성이나 효율성 측면에서 좋지만, 예상치 못한 예외가 발생할 가능성이 높은 단점이 있다. 가령 위 문제에선, phone_book의 요소들을 길이가 짧은 순서대로 dict에 담아야, 모든 번호의 접두어 번호 존재 여부를 확인할 수 있다. 반면, 후자는for loop가 하나 더 늘어나면서, 코드의 길이가 길어지는 단점이 있지만, 예외에 대한 큰 걱정 없이 검색을 할 수 있다. -
우선 빈 dict 객체인
find_number를 정의하자. 그 다음엔 요소 길이를 오름차순으로 정렬한phone_book을for loop로 순회하며 dict 안에 값을 집어 넣도록 하자.
def solution(phone_book):
find_number = {}
for number in sorted(phone_book):
find_number[number] = 1
return True-
값을 넣는 동시에 접두어 번호의 존재 여부도 확인하자. 접두어 번호는 추가하려는 값의 길이보다 무조건 짧기 때문에, 값을 집어 넣은 동시에 탐색을 해도 전혀 문제가 없다.
-
Python에서 dict 객체의
key:value를 조회할 때는 key_error가 발생하지 않도록get()를 사용해야 한다.
def solution(phone_book):
find_number = {}
for number in sorted(phone_book):
for i in range(len(number)):
if find_number.get(number[:i+1]):
return False
find_number[number] = 1
return True- 접두어 번호를 찾으려면 phone_book 안의 번호를
for loop로slicing하여 find_number 객체 안의 값과 비교해야 한다. 일치하는 값이 있을 경우false를, 없을 경우엔True를 반환하게 처리하면 된다.
다른 풀이
def solution(phone_book):
find_number = {}
for ref_number in phone_book:
find_number[ref_number] = 1
for com_number in phone_book:
for i in range(len(com_number)):
if find_number.get(com_number[:i+1]):
find_number[com_number[:i+1]] += 1
for value in find_number.values():
if value > 2:
return False
return True