[Programmers][Python] Lv.2 전화번호 목록

[문제]

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

프로그래머스

 

 

[코드]

첫 번째 풀이

- 문자열 길이 순으로 정렬하여, 길이가 적은 문자열이 길이가 긴 문자열의 접두사인지 확인을 해준다. 

- 시간복잡도는 이중 반복문이므로 O(N^2)이다. 

- 결론적으로 테스트케이스 12, 15, 19/ 효율성 테스트 4가 통과하지 못했다. 

# 접두사인지 확인하는 함수
def prefix(arr):
    for i in range(len(arr)-1):
        x = len(arr[i]) # arr[i] 가 접두사일 때 

        for j in range(i+1, len(arr)):
            s = arr[j] # x가 s의 접두사인지 확인
            if arr[i] == s[:x]:
                return False
            
        else: return True

# main
def solution(phone_book):
    arr = sorted(phone_book, key= lambda x: len(x))
    answer = prefix(arr)

    return answer

---

 

두 번째 풀이

- 문자열의 길이 순으로 정렬을 할 때, 불필요한 접두사 비교가 실행된다. (-> 사전 순으로 정렬)

- startswith 라는 메서드를 사용하여 접두사 여부를 확인한다. 

- 시간복잡도는 O(N)이다. 

startswith
- 문자열 메서드
- 특정 문자열이 주어진 접두사로 시작하는지 확인

str.startswith(prefix, start, end)
- str: 확인하려는 문자열
- prefix: 시작 여부를 확인할 접두사 문자열, 튜플 형태로 여러 접두사를 넣을 수 있음
- start(선택): 확인을 시작할 인덱스, 기본값은 0
- end(선택): 확인을 종료할 인덱스, 기본값은 문자열 끝 반환값
- 문자열이 지정된 접두사로 시작하면 True, 아니면 False

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