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

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

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

가장 먼저 제한 사항을 보고 든 생각은 시간 복잡도이다.

2중 for문을 돌게 되면 아무래도 최악의 경우에

시간 초과에서 걸릴 것 같다는 생각이 들었다.

전체 리스트의 길이가 100만 이하이기 때문이다.

 

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

 

처음에 정렬을 하지 않고 푸는 방법을 생각했다가,

정렬해서 접두어가 먼저 그 다음 번호에 있는 경우에 빠르게 탈출해야

시간 복잡도가 단축될 것이라는 생각이 들었다.

 

기존 리스트 배열을 돌면서 앞의 번호가 뒷 번호보다 짧다는 전제에서

뒷 번호의 앞 번호 길이 만큼의 접두어가 앞번호와 일치한다면 False가 될테고,

그런 경우가 없다면 True를 반환하면 된다.

 

풀고 나서 다른 사람의 풀이를 보니 startswith라는 함수를 사용하시는 분도 보았는데,

문자열1.startswith(문자열2) 라는 예시에서 문자열2가 문자열1 앞에서부터 시작되면

True를 반환하고 그렇지 않으면 False를 반환하는 동일한 내용을 가지고 있다.

 

화이팅 💪