(프로그래머스) 코딩테스트 연습 - 해시 - 전화번호 목록 (Python)

문제 : https://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 이하입니다.

 

제가 통과한 코드

def solution(phone_book):
    answer = True
    for i in phone_book:
        temp = phone_book.copy()
        temp.remove(i)
        for j in temp:
            if i in j[:len(i)] :
                return False
    return answer

저는 dictionary나 hash 함수를 쓸 생각은 전혀 들지 않더라구요...

어차피 시험에서도 이런거 생각하는 것보다 본인이 생각하는 데로 바로 문제를 푸는게 좋다고 생각합니다. 

필요하면,,, 그때 또 다시 공부하지 뭐... 

코딩테스트는 다양한 문제를 본인이 스스로 풀어보는 능력을 기르는 것이 중요하다고 생각합니다.

비슷한 유형은 다 비슷하게 풀리는 것 같더라구요.

 

또, 다른 방법으로는

1. phone_book을 정렬 후, zip을 활용 → for문을 하나로 줄일 수 있음
2. startswith 함수 활용 , itertools 모듈 활용, sorted(key = len)활용 → 여기 있는 것을 사용해보는 것도 좋을 듯합니다.
3. 정규표현식 활용
4. dictionary활용

제 방법은 뭔가 하나의 키가 선정되면 phone_book을 전체다 찾아보는 거고,

다른 사람들의 풀이를 보니 정렬 한 후 이전에 비교해봤던 키는 비교하지 않고 넘어가도록 해놨더라구요.

아마 그렇게 하면 더 빠를 것이라고 생각하는데, 뭐 일단 저도 효율성 테스트 통과하길래 ㅎㅎ 더 고민해보진 않았습니다.

 

그래도 왠지 sorted로 정렬하면 뭔가 반례가 있을 것 같은데.... 잘 모르겠네요.

sorted(key = len)은 반례가 없을 것 같지만...