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

문제 링크

문제:

phone_book의 어느 한 전화번호라도 다른 전화번호의 시작과 같은게(접두어) 존재한다면, False를 return 하고 존재하지 않다면 True를 리턴한다.

문제 풀이:

우선 접두어에 대한 설명을 잘 이해하는게 포인트.
문제에서 주어진 것 처럼

• 구조대 : 119
• 박준영 : 97674223
• 지영석 : 1195524421

phone_book을 이루고 있는 번호 (119, 97674223, 1195524421)로 시작되는 번호가 존재한다면 True를 리턴 , 존재하지 않다면 False를 리턴해야한다.

문제의 카테고리는 Hash인데 처음에는 Hash로 어떻게 풀어야할지 생각이 잘 안났다.
그래서 다른 방법으로 풀게 됬고, 정렬과 탐색을 이용해 풀게 되었다.
Hash로 풀이한건 마지막에 정리하도록 하고

• 정렬을 이용해 문자열을 정렬한다
  왜? 문자열 정렬은 알파벳 사전 순이기 때문.

["abcdef" , "abe", "abc" , "def"]

예를들어 위의 문자열들을 정렬하게 되면 아래와 같이 정렬된다.

문자열의 각각의 문자마다의 사전순으로 정렬을 하게 되어 자신과("abc") 자신의 뒤에 존재하는 문자열("abcdef")을 비교하면 자연스럽게 문제에서 필요로하는 접두어를 찾을 수 있다는게 핵심이다.

내 코드:

def solution(phone_book):
    phone_book.sort()
    print(phone_book)
    for i in range(len(phone_book) - 1):
        if phone_book[i + 1].startswith(phone_book[i]):
            return False
    return True

Hash(dictionary)를 이용한 다른 사람의 풀이:

이 문제는 굳이 hash를 사용하지 않아도 되지만 문제 출제 의도대로 푼것같다.
풀이 방식을 알아보자면,

1. phone_book에 존재하는 모든 번호들을 하나의 dictionary를 만들어 각각의 딕셔너리 key값으로 만들어 저장한다.

2. 2중 for 문을 이용해 하나의 문자열에서 tmp라는 변수에 문자 하나 하나를 더하면서 그 값이 딕셔너리에 존재하는지, 그리고 그 값이 자기 자신인지 아닌지 확인 후 조건을 만족한다면 어떤 번호가 다른 번호의 접두어인 경우이므로 False를 리턴.
   만약 모든 문자열을 검사했는데도 조건을 만족하지 않았다면 True를 리턴한다.

Hash(Dictionary)를 이용한 풀이 코드:

def solution2(phone_book):
    d1 = dict()

    for item in phone_book:
        d1[item] = 0
    print(d1)
    for item in phone_book:
        tmp = ""
        for ele in item:
            tmp += ele
            if tmp in d1 and tmp != item:
                return False
    return True

• 굳이 딕셔너리를 사용한 이유는 딕셔너리 안에서 값을 찾을때 시간복잡도가 O(1) 이기 때문. 이 문제에서는 딱히 딕셔너리를 이용하지 않아도 무방할듯 싶다.