[Python][프로그래머스] 전화번호 목록 / 해시,정렬 (Lv2)

🖇️ 링크 

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

---

🗒️ 파이썬 코드 풀이 1

def solution(phone_book):
    answer = True
    phone_book.sort()

    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False

    return answer

 

1. phone_book이 문자열임에 주목하여 sort를 해준다. 

 

2. startswith 함수로 현재 번호와 다음 번호를 비교해준다.

• 문자열 크기대로 정렬했으므로 접두사 중복 무조건 체크 가능
• 중복되는 부분은 바로 옆에 짝지어져 있음

3. 문자열 정렬로 startswith 함수를 알면 쉽게 풀 수 있는 문제

 

 

시간 복잡도 O( N·LogN )  

• phone_book의 길이 1,000,000 이하
• 1,000,000 * log2 (1,000,000)의로 본다면, 20,000,000 정도의 크기 나옴
  • 1,000,000 *  20 (약 19.93156...)  = 20,000,000
• 약 1억 밑으로 정렬 사용 가능 

 

 

🗒️ 파이썬 코드 풀이 2

def solution(phone_book):
    answer = True
    hash = {}
    
    for n in phone_book: 
        hash[n] = 1
        
    for number in phone_book:
        tmp = ""
        for i in range(len(number)):
            tmp += number[i]
            if tmp in hash and tmp != number: 
                return False
    
    return answer

 

1. Hash에서 탐색의 시간 복잡도가 O(1)을 이용해서문제를 해결한다. 

 

2. phone_book을 key 값, value는 아무거나 선언 

 

3. phone_book을 반복문 

• 이때 각각의 number를 반복문 돌면서 Hash 탐색
• 만일 hash에 탐색되는 경우 False 리턴

 

시간 복잡도 O( N)  

• for number in phone_book 부분 : O(N)
• for i in range(len(number)) 부분 : O(M)  (M은 최대 20)
• if tmp in hash (해시 탐색) 부분 : O(1)
• 따라서 시간 복잡도는 O(M*N) → O(N)

 M의 크기는 최대 20밖에 안되므로 이중 for문을 사용해도 시간복잡도가 O(N)이 되는 것이다.

 

---

📌  문제 코멘트 

def solution(phone_book):
    answer = True
    hash = {}
    
    for n in phone_book: 
        hash[n] = 1
        
    for number in phone_book:
        tmp = ""
        for i in range(len(number)):
            tmp += number[i]
            if tmp in list(hash.keys()) and tmp != number: 
                return False
    
    return answer

 

이렇게 해시를 리스트로 바꿔주는 경우는 어떻게 될까 ? 

 if tmp in list(hash.keys())

• 해시를 리스트로 바꾸는 결과이다. 
• 이렇게 할 경우 탐색에 시간이 O(N)이 된다.

 

• 결국 리스트 탐색에 시간복잡도가 O(N^2)이 되어 시간 초과가 발생한다.
• 그렇게 때문에 해당 문제 검색에서는 해시를 써야한다. 

 

이 문제를 포스팅 하는 이유는 다음과 같다.

1. 이러한 문제를 정렬로 풀이 가능한 부분
2. startswith 함수 사용 (이게 없었으면 번거로웠을 것이다.)
3. 시간 복잡도 계산 풀이 
4. 이중 for문이라고 무조건 O(N^2)이 되는거는 아님
5. 해시의 검색 시간 복잡도 O(1)을 사용한 풀이

 

여러므로 좋은 문제인 것 같다.

---

📚  문제