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

 

문제 : 전화번호 목록

바로가기

 

문제 설명

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

- 구조대 : 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

 

해답 및 해설

파이썬 (Python)

첫 풀이

def solution(phone_book):
    # 길이순 정렬
    phone_book.sort(key=len)
    num_set = set()
    
    # 앞부터 잘라가며 집합에 존재하는지 확인
    for num in phone_book:
        for i in range(1,len(num)+1):
            if num[:i] in num_set:
                return False
        num_set.add(num)
    
    return True

 우선 주어진 리스트를  문자열 길이 순서대로 정렬해주었다. 그 후 각 문자열에 대해 자른 값이 집합에 있으면 False를 리턴하고, 없으면 집합에 추가하도록 반복문을 돌렸다. 반복문이 완전히 다 돌았으면 겹치는 값이 없다는 것이므로 True를 리턴하였다.

 

 

정렬만 이용

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

 파이썬의 문자열 정렬 기능만을 이용한 풀이. sorted 함수를 그냥 이용하면 문자열이 사전순으로 정렬 되는데, 그 때 겹치는 부분이 있으면 그 두 원소들은 앞뒤로 위치하게 된다. startswith()라는 메서드를 이용한 것도 인상깊다. 파이썬에는 별별 함수들이 다 있구나

 

집합만 이용

def solution(phone_book):
    # 번호로 이루어진 집합 만들기
    num_set = set(phone_book)
    
    # 앞에서부터 인덱싱하며 집합에 있는지 확인
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in num_set and temp != phone_number:
                return False
    return True

 문자열 길이 순으로 정렬하지 않고 사전에 일단 추가한 다음, 첫 풀이와 같이 부분을 잘라가며 집합에 있는지 확인하는 방식이다. 속도는 이 방식이 살짝 빠르나 첫 풀이 방식과 거의 차이나지 않는다.