Programmers 코딩테스트 연습 전화번호 목록 Python 문제풀이.

이 문제도 역시

 

"Hash"는 정렬이다!

 

라는 것을 너무도 잘 보여주는 문제이다.

 

일단 코드를 보고가자.

 

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

아이디어는 다음과 같다.

 

1. 정수 배열을 String 배열로 바꿔준다.

2. 이를 오름차순으로 정렬하면...

사진과 같이 길이, 숫자의 배열의 유사도에 따른 정렬 결과를 얻게 된다.

 

따라서 가장 유사한 앞 뒤의 2개만 비교해주면... (앞이 prefix일 테니까)

 

우리가 원하는 정답을 얻을 수 있게 되는 것이다!

 

그냥 정렬만 하면 시간복잡도는 nlogn (퀵 or merge... 퀵은 n^2도 가능하지만 평균적으로)

 

정렬 후 탐색은 1중 for이지만 내부적으로 n의 탐색을 할 것 같다. (string match... 더 좋은 알고리즘도 있을것 같은데... 최악으로는...ㅋㅋ)

 

따라서 N^2일 것 같지만. 이 문제는 어떻게 풀 것인가? 를 생각하는 발상이 더욱 중요했던 것 같다.