[해시] 프로그래머스 level 2 전화번호 목록 (Python 파이썬)

💡문제 링크

프로그래머스

 

💡문제 분석 요약

1. 전화번호부에 적힌 전화번호를 담은 리스트 phone_book(길이는 100만 이하, 메모리 4MB 이하)
2. 모든 전화번호에 대해서 접두어 관계가 하나라도 형성되면 false 리턴

 

💡알고리즘 설계

1. phone_book 리스트 정렬

2. 앞에서부터 완전 탐색 진행

3. i번째 원소가 i+1번째 원소의 앞부분과 일치하면 answer를 False로 바꾸기

4. answer 리턴

💡코드

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

 

💡 오답 풀이

def solution(phone_book):
    answer = True
    phone_book.sort(key = len) 
    for i, p1 in enumerate(phone_book): 
        for p2 in phone_book[i + 1: len(phone_book)]: 
            if p1 == p2[:len(p1)]:
                answer = False
                break
    return answer

처음에 이 코드를 작성했을 때, 정확성 테스트는 다 통과했는데 효율성 테스트에서 다 시간 초과가 떴다..

아무래도 이중 반복문을 써서 그런 것 같다.

아니 그러면 이중 반복문 안 쓰고 어떻게 하는거지..?

**초기 알고리즘 설계**

1. 전화번호 길이를 기준으로 phone_book 정렬(접두어가 될 가능성이 높은 전화번호를 맨 앞으로)

2. 앞에서부터 전화번호 탐색

3. i번째 전화번호를 골랐을 때, i+1번째 전화번호부터 끝까지 탐색

4. i번째 전화번호가 i+1번째 전화번호의 접두어일 경우 answer를 false로 바꾸고 break로 끝내버리기

5. answer값 리턴

접두어가 있으면 false, 없으면 true

 

💡 다른 풀이

...

 

💡 느낀점 or 기억할정보

3. i번째 원소가 i+1번째 원소의 앞부분과 일치하면 answer를 False로 바꾸기

이걸 생각해내야하는 문제

왜 초반에는 굳이굳이 sort(key = len)을 써서 문자열 길이순으로 정렬하려 했는지 참..