문제 설명
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 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 |
입출력 예 설명
입출력 예 #1
- 앞에서 설명한 예와 같습니다.
입출력 예 #2
- 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
입출력 예 #3
- 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.
나의 접근 1
전화번호의 접두사를 묻는 문제라서 2중포문으로 접두사로 붙어있는지 확인
def solution(phone_book):
# 접두사로 쓰일 전화번호를 꺼내는 for문
for i in range(len(phone_book)):
cnt=0 #카운트 초기화
# 접두사를 비교할 전화 번호를 꺼내는 for문
for j in range(len(phone_book)):
# 접두사로 쓰인 전화번호와 동일 길이로 슬라이싱한 문자열 비교
if phone_book[j][:len(phone_book[i])] == phone_book[i]:
cnt+=1
if cnt==2: # 자기자신도 비교 하기에 두번 카운트 되면 리턴
return False
return True정확도는 통과 하였으나 효율성 3번 4번에서 시간초과가 나옴
나의 접근 2
효율성에서 문제가 생겼기에 나의 코드의 시간복잡도를 확인하고 시간복잡도가 낮아지는 방향으로 코드를 수정하려고 시도함
def solution(phone_book):
for i in range(len(phone_book)):
cnt=0 #할당 연산
for j in range(len(phone_book)):
if phone_book[j][:len(phone_book[i])] == phone_book[i]: #비교 연산
cnt+=1 # 산술 연산
if cnt==2: # 비교 연산
return False
return True확인결과 값이 True 가 리턴되기 위해선 O(n+3n^2) 이라는 시간 복잡도를 가짐
시간복잡도를 확인해보고 코드를 수정하려 했지만 어느 부분을 수정 해야 할지 감을 잡지 못하였다
나의 접근 3
접근을 못하겠으니 일단 정렬을 해보았다(정렬을 한다면 속도가 빨라지지 않을까 하는 얄팍한 생각)
def solution(phone_book):
phone_book.sort()
for i in phone_book:
cnt=0
for j in phone_book:
if j[:len(i)] == i:
cnt+=1
if cnt==2:
return False
return True하지만 역시나 효율성 3번4번은 통과할수없었다
나의 접근 4
정렬된 리스트를 보고 모든 리스트에 접두사를 탐색할 필요가 없음을 인지했다
정렬시에 먼저 오는 값이 뒤의 값의 길이보다 짧기에 바로 뒤의 값만 확인 하면 된다
def solution(phone_book):
phone_book.sort()
for i in range(len(phone_book)-1):
if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
return False
return True정답!!
