문제 설명
전화번호부에 한 번호가 다른 번호의 접두사인 전화 번호가 나열되는지 확인하려고 합니다.
전화번호가 다음과 같을 경우 구조 전화번호는 영석의 전화번호 앞자리입니다.
- 구조대: 119
- 박준영: 97 674 223
- 지영석: 11 9552 4421
전화번호부의 전화번호를 포함하는 phone_book 배열이 solver 함수 매개변수로 주어지면 주어진 번호가 다른 번호의 접두어이면 false를 반환하고 그렇지 않으면 true를 반환하도록 solver 함수를 작성합니다.
제한
- phone_book의 길이는 1 이상이어야 하며 1,000,000을 초과할 수 없습니다.
- 각 전화번호는 1에서 20 사이여야 합니다.
- 동일한 전화번호는 두 번 포함되지 않습니다.
입력/출력 예시 phone_bookreturn
| (“119”, “97674223”, “1195524421”) | 잘못된 |
| (“123″,”456″,”789”) | 진실 |
| (“12″,”123″,”1235″,”567″,”88”) | 잘못된 |
I/O 예시 설명
I/O 예제 #1
이전 예제와 동일합니다.
I/O 예제 #2
숫자는 절대 다른 숫자의 접두사가 아니므로 대답은 참입니다.
I/O 예제 #3
첫 번째 전화번호 ’12’는 두 번째 전화번호 ‘123’의 지역번호입니다. 답이 잘못되었습니다.
생각의 흐름
1. 문자열 목록의 단어가 다른 단어의 시작 부분과 일치하면 False, 그렇지 않으면 true
2. for 문으로 문자열을 하나씩 확인합니다. 입력 데이터 크기는 최대 100만 개입니까?
3. 정렬(숫자가 아닌 문자열로 알파벳순으로 정렬)을 사용하여 동일한 부분을 빠르게 검토
문제 핵심 및 알고리즘
문자열 사용 문제입니다. 효율성으로 정렬그리고 문자열 비교
import re
def solution(phone_book):
answer = True
phone_book.sort()
for i in range(len(phone_book)-1) :
#if re.match(phone_book(i), phone_book(i+1)) :
if phone_book(i)==phone_book(i+1)(:len(phone_book(i))) :
return False
return True문제를 풀면서 고민했던 부분
1. re.match의 시간적 복잡성
처음에는 주석 처리된 부분과 같이 코드를 작성했지만, 시간 초과 후 목록 인덱싱으로 한 번 전환했습니다. 맞습니다.
-> 매치의 시간복잡도가 크기 때문에 인덱스로 접근하여 시간을 줄여야 한다.
다른 풀을 참고하면서 알게 된 점
def solution(phoneBook):
phoneBook = sorted(phoneBook)
for p1, p2 in zip(phoneBook, phoneBook(1:)):
if p2.startswith(p1):
return False
return True다시, p2가 p1로 시작하는지 확인하기 위해 숫자를 반복하는 stratswith 함수를 사용하여 먼저 정렬했습니다. 훨씬 쉽게
=> list1.startswith(list2): list1이 list2로 시작합니까?