문제 내용

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
제한 사항
phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.
같은 전화번호가 중복해서 들어있지 않습니다.
해당 문제 링크:https://programmers.co.kr/learn/courses/30/lessons/42577

결국 핵심은 이거다.
1. 번호를 하나 고른다.
2. 내번호 크기만큼 비교하는 녀석 문자열 슬라이싱 해준다
3. 내번호와 비교해서 일치하면 False 리턴
4. 위의 과정이 전부 끝나도 False가 안나오면 Ture를 리턴한다.

코드로 구현해보자.

def solution(phone_book):
    
    for i in phone_book: # 번호를 하나 고른다.
    	# 폰북에서 위의 번호와 크기를 맞추고 비교한다.
        phone_ls = [num for num in phone_book if num[:len(i)] == i] 
            
        if len(phone_ls) > 1: # 자기자신을 포함하므로 1이상이 되어야 한다.
            return False
    
    else: #for 문이 다돌도록 없으면 True를 리턴 
        return True

바로 테스트!

굿

바로 제출 후 채점

훗 존나 쉽군.. ㅋ

!!!! 나...니?

하 뭐가 문제냐... 너무 쉽게 푼다했다.. 이녀석 쉽지 않은 녀석일지도..?

지금 O(N^2)의 시간복잡도를 어떻게 줄일 것인가에 대해 많은 고민을 진행했다.

효율성 때문에 한 2시간을 헤메다가 이게 해시를 이용하면 좋을 것 같다는 생각이 문득 들었다.

위의 핵심을 조금 비틀었다.
1. 번호 길이를 하나 고른다.
2. 번호의 길이와 일치하는 녀석들을 골라준다.
3. 번호 길이보다 큰녀석들을 번호 길이만큼 앞에서 부터 슬라이싱 해준다
4. 2번에서 도출한 번호와 3번에서 도출한 번호와 비교해서 일치하면 False 리턴
5. 위의 과정이 전부 끝나도 False가 안나오면 Ture를 리턴한다.

해시 테이블 사촌 set 너를 활용해 주겠어!

def solution(phone_book):
    for l in range(1, 21):
        """
        1.문자열을 길이 순으로 뽑은 후 비교군을 길이에 맞춰 조정한다. 
        2. select와 comp를 비교한다.
        3. 일치하면 False 불일치하면 True를 리턴한다.
        """
        phone = {pb for pb in phone_book if len(pb) == l}
        comparision = {pb[:l] for pb in phone_book if len(pb) > l}
        
        if phone & comparision:
            return False
    else:
    	return True

위의 코드의 시간복잡도는 O(N^2)처럼 보이나, 전화번호의 길이는 20까지 이므로 결국 O(N)이다.

이런 차이는 결국 위의 내코드와 엄청난 차이를 만들어 낸다.

내 코드는 phone_book의 길이가 21 이상부터 아래 코드보다 연산의 횟수가 더 많아진다.

직관적이고 간단해보이지만, 도출하는 과정이 힘들었던 이 코드 꼭꼭 씹어먹어야지.