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

< 첫 번째 풀이 방식 >

접두어가 될 번호를 대상으로 검사하려고 했다.

 

 전화번호부에 ["11","119","45234"] 가 있다면, 11, 119, 45234에 대해서 for loop를 돌고, 내부 for loop로 나머지 번호에 대해서 검사한다.

 이때 11, 119, 45234를 for 도는 방식이면 나머지 비교번호를 이 길이만큼으로 잘라야 해서, 이중 for loop를 쓸 수 밖에 없다. 이렇게 되면 시간초과가 발생한다.

def solution(phone_book):
    dict1 = {}
    for i in range(len(phone_book)):
        dict1[i] = phone_book[i]
    for num in phone_book:
        if any(nums.startswith(num) and nums != num for nums in dict1.values()):
            return False
        
    return True

 

도저히 시간초과를 내지 않을 방법(이중 for loop를 돌지 않을 방법)을 모르겠어서,, (중간에 return, break를 넣어줘도 시간초과가 발생한다.) 며칠의 고민 끝에 답을 봤다. 초기에는 답을 보고도 왜 ..? 싶었는데, 정답 방식은 다음과 같다.

 

< 정답 풀이 방식 >

 전화번호부에 ["11","119","45234"] 가 있다면 11, 119, 45234가 다른 번호의 접두어인지 확인하는 방식이 아니다. 그 반대의 방식이다.

즉 11의 접두어는 1 또는 11 / 119의 접두어는 1, 11, 119 / 45234의 접두어는 4, 45, 452, 4523, 45234이다.

이렇게 for문을 이중으로 구성하면 .. 리스트를 순회하는 방식으로 검사하지 않고, 각 대상 (11, 119, 45234) 에 대해서 하나씩 검사 문자를 늘리면서 이 가능 접두어가 집합 또는 딕셔너리(해시)에 있는가 검사하면 시간이 단축된다.

 

def solution(phone_book):     
    phone_hash = set(phone_book)    
    for phone in phone_book:        
        temp_num = ""                
        for digit in phone:            
            temp_num += digit
            if temp_num in phone_hash and temp_num != phone:                
                return False    
    return True

 

오답 코드를 내었다면,, 내가 생각한 한 가지 방식 말고 어떻게 진행시킬 수 있는가..에 대해 고민해야한다..(발상의 전환)

 

* 또 이중 for loop에 따른 시간초과 문제에서, sort를 사용하면 sort된 결과에서 앞부분까지만 검사하여 그에 따른 뒷부분은 모두 함께 오케이 시킬 수 있다. 이에 따른 시간 단축 효과도 매우 크다고 한다.

( sort 시키면 앞 부분이 같은 문자 두 가지 (즉 하나가 다른 하나의 접두어임) 는 서로 붙어있을 수밖에 ...)

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i]==phone_book[i+1][:len(phone_book[i])]:
            return False
    return True