[프로그래머스/Lv2] 전화번호 목록
문제
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 한다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사이다.
- 구조대 : 119
- 지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book이 매개변수로 주어질 때,
어떤 번호가 다른 번호의 접두어인 경우가 있으면 False 그렇지 않으면 True를 반환하는 함수를 만들어야 한다.
제한사항
1. phone_book의 길이는 1 이상 1,000,000 이하이다.
2. 각 전화번호의 길이는 1 이상 20 이하이다.
3. 같은 전화번호가 중복해서 들어있지 않다.
코드
def solution(phone_book):
answer = True
sorted_phone_book = sorted(phone_book)
for i in range(len(phone_book)-1):
if sorted_phone_book[i] == sorted_phone_book[i+1][:len(sorted_phone_book[i])]:
return False
return answer
설명
십중팔구 문자열의 길이를 기준으로 phone_book을 정렬해서 처음부터 하나씩 전부 비교해 볼텐데
그러면 효율성 테스트 케이스 3, 4번에서 시간 초과가 난다.
숫자가 아닌 문자열 배열은 정렬하면 사전 순으로 정렬된다.
이 문제에서 주어진 배열의 원소들이 문자열인 것에 주목하자.
사전 순으로 정렬하면 첫번째 원소부터 마지막 원소까지 전부 비교할 필요 없이
현재 원소와 그 뒤 원소만 비교해도 된다.
코드 구현 자체는 어렵지 않다.
answer = True
반환할 값인 answer를 True로 초기화 해둔다.
sorted_phone_book = sorted(phone_book)
입력으로 들어온 phone_book을 정렬한다.
for i in range(len(phone_book)-1):
if sorted_phone_book[i] == sorted_phone_book[i+1][:len(sorted_phone_book[i])]:
return False
0부터 phone_book의 길이-1 까지 숫자들을 꺼내며 반복한다.
만약 sorted_phone_book[i]가 sorted_phone_book[i+1]의 접두어(슬라이싱을 통해 구현 [:len(sorted_phone_book[i])])라면
False를 반환한다
return answer
모든 비교가 끝나고 접두어인 경우가 없다면
answer를 반환한다.
'코딩테스트 > 연습문제' 카테고리의 다른 글
[프로그래머스/Lv2] 타겟 넘버 (0) | 2022.11.03 |
---|---|
[프로그래머스/Lv2] k진수에서 소수 개수 구하기 (0) | 2022.11.03 |
[프로그래머스/Lv2] [1차] 뉴스 클러스터링 (0) | 2022.11.02 |
[프로그래머스/Lv2] 프린터 (0) | 2022.11.01 |
[프로그래머스/Lv2] 기능개발 (0) | 2022.11.01 |