알고리즈 풀이: [프로그래머스] 전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577

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

문제 설명

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

 

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

 

구조대 : 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입니다.

 

---

문제 풀이

해시에 속하는 문제이지만 해시를 사용하지 않고 깔끔하게 풀 수도 있습니다.

 

 

해시로 문제를 접근해봅시다.

해시를 활용한 풀이

해시 테이블의 키에 전화번호를 저장합니다. 이후 각각의 전화번호에 대해서 접두어를 찾고 접두어가 해시 테이블에 키로 있는지 확인합니다. 있을 경우 false를 반환합니다.

 

 

하지만 사실 전화번호 값만을 비교하면 되기 때문에 해시를 사용할 필요가 없습니다.

 

해시 테이블이 의미를 지니는 것은 키와 그에 대한 값이 대응될 때입니다. 하지만 이 문제에서 전화번호끼리 비교하는 것이 중요한 것이지 전화번호에 어떠한 값이 대응되었는지가 중요하지 않습니다. 따라서 전화번호 두 개를 선택해서 비교하고, 그 결과 접두사 관계라면 false를 반환합니다.

 

소스 코드

해시를 사용한 풀이

def solution(phone_book):
    # 해시를 사용한 풀이
    hash_table = {phone_number:1 for phone_number in phone_book}
    
    for phone_number in phone_book:
        prefix = ''
        # 전화번호에서 마지막 글자만을 제외하고 접두사를 구한다. (ex, 119 -> 1, 11)
        for number in phone_number[:-1]:
            prefix += number
            # 접두사가 해시 테이블의 키에 있다면 접두사 관계의 전화 번호가 있는 것이다.
            if prefix in hash_table.keys():
                return False

    return True

 

해시를 사용하지 않는 풀이

import itertools


# 해시를 사용하지 않은 풀이
def solution(phone_book):
    # itertools 라이브러이에서 조합을 구하는 메서드 combinations 사용. 2개의 전화번호를 구한다
    for p1, p2 in itertools.combinations(phone_book, 2):
        # 전화번호가 접두사 관계인지 파악한다.
        if p1.startswith(p2) or p2.startswith(p1):
            return False
    return True

 

프로그래머스 화면

github 주소: https://github.com/dhsong95/-PRACTICE-Programmers-Algorithm/blob/master/level%202/%EC%A0%84%ED%99%94%EB%B2%88%ED%98%B8%20%EB%AA%A9%EB%A1%9D.py

dhsong95/-PRACTICE-Programmers-Algorithm