전화번호 목록 - 프로그래머스

코딩테스트 연습 - 전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

---

간단하게 요악하면 '누군가의 전화번호가 다른 누군가의 전화번호로 시작하는가?' 이다.

 

내 해결 방법은 이렇다.

1. 전화번호 목록을 정렬한다.
2. 연속된 전화번호의 뒷 전화번호가 앞 전화번호로 시작하는지 확인한다.

만약, ['112', '248', '11257']이 입력이라면, 정렬했을 때 ['112', '11257', '248']이 된다.
정렬 기준상 한 숫자가 다른 숫자의 시작이라면, 더 길이가 짧은 쪽이 앞으로 온다. 왜냐하면 비교도중 문자열이 남아있으면 더 큰 값으로 처리되기 때문이다. 이를 이용하여 앞숫자가 뒷숫자의 시작인지 확인하면 된다.

 

위의 해결 방법을 코드로 해결하기 위한 순서는 다음과 같다.

1. 전화번호 목록을 정렬한다.
2. 모든 자리에 대하여 다음을 실행한다. (마지막 자리는 제외한다. 다음 데이터가 없기 때문)
   1. 다음 자리의 데이터가 해당 자리의 데이터로 시작하는지 확인한다.
   2. 2-1을 만족한다면 false를 반환한다.
3. 모든 자리에 대하여 만족하지 않았다면 true를 반환한다.

 

위의 순서를 코드로 작성하면 다음과 같다.

def solution(phone_book):
    answer = True
    
    # 1. 전화번호 목록을 정렬한다.
    phone_book = sorted(phone_book)
    
    # 2. 모든 자리에 대하여 (마지막 자리 제외)
    for i in range(len(phone_book) - 1):
    	# 2-1. 뒷숫자가 앞숫자로 시작하는지 확인한다
        if phone_book[i + 1].startswith(phone_book[i]):
            # 2-2. 만족할 경우, false를 반환한다.
            answer = False
            break
            
    # 3. 모든 자리에 대하여 만족하지 않을 경우 true를 반환한다
    return answer