[programmers] 전화번호 목록

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

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

 

 

 

 

처음 코드

def solution(phone_book):
    answer = True
    for i in range(len(phone_book)):
        for j in range(len(phone_book)):
            if i == j:
                continue
            else:
                len_ = len(phone_book[i])
                if phone_book[i] in phone_book[j][0:len_]:
                    return False
    return answer

정답은 맞았지만, 효율성 마지막 2문제 실패.

이중 for 문이라 시간이 오래 걸리고, 자기 자신을 제외한 모든 문자열끼리 비교한다.

 

 

두 번째 코드

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

※ 문자열 sort의 특징을 이용하자!

 

위와 같은 문자열을 정렬하면

전체 문자열 길이와 상관 없이 614566634가 온다

즉, 만약 접두어가 존재한다면, 해당 문자와 바로 뒷 순서의 문자와 비교하면 되기 때문에 for문 하나로 해결 가능하다.

또 하나의 접두어만 존재해도 바로 false가 되기 때문에 바로 return 해주면 된다.