프로그래머스 Lv2 전화번호 목록 (python)

전화번호 목록

풀이

처음방법으로 풀었을 때, 잘 넘어갔지만, 효율성에서 문제가 생겼었다.

# 전화번호 부의 한 번호가 다른 번호의 접두어인 경우가 있는지 확인
# 있으면 False, 없으면 True
# .startswith()를 활용
def solution(phone_book):
    phone_book_sort = sorted(phone_book)
    for i in range(len(phone_book)):
        for j in range(i+1, len(phone_book)):
            if phone_book_sort[j].startswith(phone_book_sort[i]):
                return False
    return True

그래서 보다 보니 내가 사용하기 위해 phone_book 이미 정렬을 해둔 게 있다.
정렬을 해뒀다면, 이를 더 잘 이용해먹어야지.

정말로 잘 정렬된 문자열 리스트라면 내가 120이라면, 내 뒤에는 1201231 또는 121~~ 등이 될 것이다.
따라서 for문을 2번 적을 필요 없이 나와 내 뒤에 녀석만 확인하면 끝이다.
이렇게 하니 통과가 되었다.

# 전화번호 부의 한 번호가 다른 번호의 접두어인 경우가 있는지 확인
# 있으면 False, 없으면 True
# .startswith()를 활용
def solution(phone_book):
    phone_book_sort = sorted(phone_book)
    for i in range(len(phone_book) - 1):
        if phone_book_sort[i+1].startswith(phone_book_sort[i]):
            return False
    return True

다른 사람 풀이

해쉬로 푼 방법이다.
이렇게는 어떻게 풀지 했는데 역시 똑똑한 사람들이 많다.
1. answer = True로 미리 설정
2. 전화번호를 입력시킬 hash_map 딕셔너리 생성.
3. for문을 돌면서 phone_number에 "119" : 1의 형식으로 입력
4. 접두어 여부를 확인하기 위해, 전화번호를 for문으로 확인, 하면서 temp변수를 이용
4-1. temp 변수는 문자열로 다음처럼 저장 '1', '11', '119'
5. temp가 만들어지는 과정에서 temp가 hash_map에 있는지 확인하고, 이게 temp를 만들고 있는 전화번호와 동일하지 않다면, 현재 temp를 만드는 데 사용하고 있는 temp는 접두어가 되는 전화번호. 따라서 False 반환
6. 모든 반복문을 돌았는데 return 되지 않았으니, True반환

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer