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

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

프로그래머스

이 문제는 알고리즘 분류가 해시로 되어있긴 하지만, 해시를 사용하지 않고도 풀 수 있다.

처음에는 이중 for문으로 각요소가 다른 요소의 접두어인지 확인하게끔 코드를 짰다. 

def solution(phone_book):
    phone_book.sort()
    n = len(phone_book)
	for i in range(n):
    	for j in range(n):
        	if phone_book[i] != phone_book[j] and phone_book[j].startswith(phone_book[i]):
            	return False
    return True

모든 테스트케이스는 통과하였지만, 효율성 테스트에서 두 개의 테스트를 통과하지 못했다.

그래서 약간 수정한 코드가 아래와 같다. (인덴트가 왜 이렇게 되는지 모르겠다.;;)

def solution(phone_book):
    phone_book.sort()
    n = len(phone_book)
	for i in range(n):
    	for j in range(i, n):
        	if phone_book[i] != phone_book[j] and phone_book[j].startswith(phone_book[i]):
            	return False
    return True

반복의 횟수가 조금 줄긴 했지만, 여전히 시간 복잡도는 O(n^2)이다.

 

그래서 질문하기 페이지에서 힌트를 얻은 것이, 파이썬의 sort() 메소드의 기본에 대해 잘 찾아보라는 것이었다.

그걸 알면 해당 요소와 바로 다음 인덱스의 요소만 비교해도 된다는 것이다.

예시를 들어보자.

input : ["12". "123", "887", "567", "1235", "88] 

위의 input을 sort()메소드로 정렬하면,

["12", "123", "1235", "567", "88", "887"] 이 된다.

그렇기 때문에, 어떤 번호가 다른 번호의 접두어가 될 수 있다면 그 어떤 번호는 반드시 다른 번호의 한 순서 앞에 정렬되는 것이다.

 

그래서 제출한 최종 코드는 아래와 같다.

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

반복문도 1개 밖에 없기 때문에 시간복잡도도 O(n)으로 훨씬 줄었고, 모든 효율성 테스트도 통과할 수 있었다.