[프로그래머스/Python] 알고리즘고득점Kit-해시-전화번호 목록

📌 문제링크

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

📌 문제설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

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

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.
• 같은 전화번호가 중복해서 들어있지 않습니다.

# 입출력 예제 

📌 풀이과정

# 처음 시도 

• 길이순으로 짧은 것이 다른 녀석의 접두어가 될 확률이 높다고 생각했다. 그래서 길이 순으로 먼저 정렬을 했고, 
• 각 요소에 대해서 그 녀석으로 시작하는지 이중for문을 돌렸다. 
• => testcase는 모두 통과했지만, 효율성 테스트3,4 실패했다. 

phone_book.sort(key=lambda x:len(x))
for i in range(len(phone_book)):
	key = phone_book[i]
	kLen = len(key)
	for j in range(i+1, len(phone_book)):
    	if key == phone_book[j][0:kLen]: 
    		#print(key, phone_book[j])
    		return False
    return True

 

# 구글링 후 

• 이중 for문을 돌리는 게 일단 비효율적이라곤 생각이 들었다. 
• 배열 phone_book을 정렬할 때, 앞 숫자들끼리 비슷한 것끼리 묶이는 방법이 뭐 없나 생각을 했다. 
• ✅ 문자열끼리 비교할 때는 맨 앞 문자부터 비교해 나간다는 점!!! 을 잊고 있었다. 
  • 첫번째 예제의 경우 ['119', '1195524421', '97674223']과 같이. 
  • 내가 원하던 게 이거다. 그러면 앞 뒤끼리 비교해나갈 때 False가 나올 확률이 높아진다.

📌 풀이코드 

# 12:56 start 1:18 end (search yes)
def solution(phone_book):
    answer = True
    phone_book.sort() # 문자열 정렬할 때 맨 앞 문자부터 하나씩 비교한다는 점을 알고 있으면
    #print(phone_book)
    # 첫번째 예제는 이렇게 정렬된다. ['119', '1195524421', '97674223']
    for i in range(len(phone_book)-1):
        if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
            return False 
    return True