[프로그래머스]level2-전화번호 목록-Python[파이썬]

문제링크

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

문제설명

알고리즘

1. 정렬을 이용한 풀이

문자열 정렬 기준 :
1) 첫번째 문자를 아스키 코드를 기준으로 정렬,
2) 동일한 경우 두번째 문자를 아스키 코드를 기준으로 정렬,
3) 동일한 경우 세번째 문자를 아스키 코드를 기준으로 정렬
...

input : ["12", "123", "1235", "567", "88"]
-->
output : ['12', '123', '1235', '567', '88']

input : ["119", "97674223", "1195524421"]
-->
output : ['119', '1195524421', '97674223']

이렇게 문자열을 정렬시키면 접두사가 비슷한? 전화번호끼리 모이게된다.
그 후 for문을 돌면서 전화번호를 비교한다.

• n번째 전화번호를 비교대상으로 지정할 경우(comp = phone_book[n])
  - n번째 전화번호와 n+1번째 전화번호의 접두사가 일치한다면 false를 return하게만들고
  - n번째 전화번호와 n+1번째 전화번호의 접두사가 일치하지 않다면 n번째 전화번호는 n+1번째 이후의 전화번호와도 일치하지 않으므로 for문으로 다시 돌아가 비교대상 전화번호를 n+1번째 전화번호로 바꾼다.
  (comp = phone_book[n+1])
  

이렇게 전화번호부를 모두 다 돌게되면, 접두사 전화번호가 존재하지 않은 것이므로 true를 return한다.

* 코드

def solution(phone_book):
    phone_book.sort() 
    print(phone_book)
    for i, phone in enumerate(phone_book):
        comp = phone_book[i]
        if i+1 < len(phone_book):
            if comp == phone_book[i+1][:len(comp)]:
                return False
    return True

* 보완점

어떤 문자열s1이 특정 문자열s2로 시작하는지 확인하는 함수 : s1.startswith(s2) 를 쓰면 코드가 더 간결해질 듯

2. 해쉬를 이용한 풀이

코드

def solution(phone_book):
    # 정렬
    phone_book.sort(key=len)
    hash_table = {}
    # [12, 88, 123, 567, 1235]
    # 맨 처음 가장 짧은 길이를 저장. min.
    min_len = len(phone_book[0])
    for target in phone_book:
        # loop마다 본인 정보를 hash table에 저장.
        hash_table[hash(target)] = target  # hash(key) : 전화번호(value)
        # min길이부터 +1씩 해서 본인 길이까지 hash table에서 검색.
        # 있으면 false, 없으면 true-계속 진행.
        for i in range(min_len,len(target)):
            try:
                if hash_table[hash(target[0:i])]: # target의 접두사가 hash_table에 존재하는 경우 -> false 반환
                    return False
            except KeyError: # 존재하지 않는 경우
                pass
    return True