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

풀이 참조: https://youtu.be/4-iyppqNCyg

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

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

위 유튜브 영상을 보고 정리하였습니다. 개발자로 취직하기 님께 감사드립니다. 

 

Solution 1

 

이중포문을 쓰고 if 문 2개로 서로 접두어인지 확인한다. 

테스트케이스 2개가 시간초과가 뜬다. 

# Loop를 활용한 솔루션 : 시간초과 뜸.
def solution_Loop(phone_book):
    # 1. 비교할 A 선택
    for i in range(len(phone_book)):
    # 2. 비교할 B 선택
       for j in range(i+1, len(phone_book)):
    # 3. 서로가 서로의 접두어인지 확인한다.
           if phone_book[i].startswith(phone_book[j]):
               return False
           if phone_book[j].startswith(phone_book[i]):
               return False

    return True

 

Solution 2

 

정렬을 하고 zip을 활용해서 배열의 2번째부터 시작하는 배열과 원래 배열을 묶어서, 비교하여 for문을 한 개로 줄인다.

시간초과없이 잘 통과한다.  

# Sorting / Loop를 활용한 solution
def solution_sorting(phone_book):
    # 1. 전화번호 sorting 한다
    phone_book.sort()
    
    # 2. sorting한 전화번호를 2개씩 확인해서 접두어인지 본다.
    for p1, p2 in zip(phone_book, phone_book[1:]):
        if p2.startswith(p1):
            return False

    return True

Solution 3

해쉬를 활용한 풀이

각 숫자를 키로  해시맵을 만들어 놓고 그 해당 키로 검색을 하는 방법이다.

 

jubdoo 라는 변수에 숫자를 하나씩 붙이면서 해시맵에 해당하는 접두 숫자가 있는지 확인한다. (if jubdoo in hash_map)

jubdoo가 지금 붙여지는 숫자가 아닌 다른 숫자와 일치하는지 동시에 파악한다. (and jubdoo != phone_number)

def solution(phone_book):
    # 1. Hash map 을 만든다.
    hash_map = {}
    for number in phone_book:
        hash_map[number] = 1

    print(hash_map)
    # 2. 접두어가 Hash map 에 존재하는지 찾는다.
    for phone_number in phone_book:
        jubdoo = ''
        for number in phone_number:
            jubdoo += number
            # 3. 접두어를 찾아야 한다. (기존 번호와 같은 경우는 제외한다)
            if jubdoo in hash_map and jubdoo != phone_number:
                return False

    return True