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

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

프로그래머스

 

[풀이1] string sort 이용

def solution(phone_book):
    
    # (1) 리스트 요소를 정렬 (string이니 a,b,c... 1,2,3... 순)
    phone_book.sort() # O(N Log N)
    
    # (2) 원소들 서로 앞뒤로 비교
    for i in range(len(phone_book)-1): # O(n)
        front = phone_book[i]
        back = phone_book[i+1]
        if (front==back[:len(front)]):
            return False        
    return True

• string 리스트를 정렬했을때 어떻게 되는지를 생각할수만 있으면 이거 쉽게 풀리겠다 싶었음.
• O(n) + O(N Log N) = O(N Log N)

 

[풀이2] 해시 - set 이용

def solution(phone_book):
    # (1) set에 key값 세팅
    my_set = set(phone_book)

    # (2) prefix substring 여부 확인    
    for phone_num in phone_book:
        sub_str = ""
        for i in range(len(phone_num)):
            sub_str += phone_num[i]
            if (sub_str in my_set and sub_str!=phone_num):
                return False
    
    return True

• 프로그래머스 다른 사람 풀이 보니까 dict 썼던데 어짜피 dict의 value 부분은 필요없으니 set을 쓰는게 더 낫겠다 싶었음
• 시간복잡도 O(n) * O(k) ....? 인거같은데 맞나..