[프로그래머스/Lv2] 전화번호 목록

2022. 11. 2. 13:04

문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 한다.

 

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사이다.

- 구조대 : 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를 반환한다.

BELATED ARTICLES

more