[프로그래머스] 전화번호 목록 파이썬

programmers.co.kr/learn/courses/30/lessons/42577

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

1. 첫 번째 시도

정확성: 75.0

효율성: 8.3

합계: 83.3 / 100.0

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

- 입력값을 정렬하고, 나머지 문자열들과 모두 하나씩 비교해봤지만 정확성과 효율성이 떨어졌다.

 

2. 두 번째 시도

정확성: 83.3

효율성: 8.3

합계: 91.7 / 100.0

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)):
        for j in range(i+1, len(phone_book)):
            if phone_book[i][0] != phone_book[j][0]:
                break
            if phone_book[i] in phone_book[j]:
                return False
    return True

- 문자열에서 처음 문자가 같지 않으면 넘기는 식으로 했지만 역시나 정확성과 효율성이 떨어졌다. 이때, 인접한 문자열만 비교해주면 된다는 사실을 깨달았다. (정렬을 했기 때문에 인접한 문자열에서 포함 관계가 나오지 않는다면 그 이후에도 나올 수가 없다.)

 

3. 세 번째 시도

정확성: 79.2

효율성: 16.7

합계: 95.8 / 100.0

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

- 인접한 문자열끼리만 비교해주었지만 효율성은 조금 올랐지만, 정확성 부분에서 더 떨어졌다.

---

SOLUTION

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

 

startswith() 함수는 문자열의 앞부분만을 비교하기 때문에 정확도와 효율성을 높일 수 있다.

def startswith(source, prefix):
    return source[:len(prefix)] == prefix

 

in 연산자는 문자열 전체를 검토하기 때문에 이 문제에서 사용하면 정확도가 떨어진다.

예를 들어, phone_book[i]가 '123'이고, phone_book[i+1]이 '12400000000000000123'이어도 True가 되기 때문이다.

또한, 시간 복잡도 면에서도 문자열 처음부터 끝까지 확인하기 때문에 효율성이 떨어진다.