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

문제 : 

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

풀이 : 

1. 시간 초과 코드 

- 이중 루프를 돌아야 하기 때문에 시간 초과 발생 

- phone_book[j].startswith(temp): 부분에서 temp.startswith( phone_book[j] 상황도 고려해야 하므로 적절한 코드가 아님 

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

 

2. 정답 코드

- 사전 순으로 정렬 하게 되면 길이가 짧거나 사전 순으로 앞선 것이 무조건 앞에 오기 때문에 항상 뒷번호.startswith(앞번호) 형태만 검사하면 된다. 

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

 

---

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42577