해쉬_전화번호 목록

접근 방식

1. 완전 탐색

문제를 읽고 가장 먼저 생각나는 것은 완전 탐색일 것이다.

리스트의 원소 1개를 기준으로 전체를 탐색하며 접두어가 되는지 확인하는 것이다.

이 방식을 사용한다면 1) 리스트 원소 마다 2) 전체를 탐색하며 접두어가 되는지 확인 하는 과정이 필요하고

2중 Loop 으로 구현이 가능하다.

하지만, 문제의 제약조건 [phone_book의 길이는 1 이상 1,000,000 이하입니다.] 을 확인하면 이 방식은 1,000,000 x 1,000,000 의 시간이 걸리는... 관계로 제외하였다.

 

2. sort/Loop

2중 Loop를 1중 Loop으로 변환 할 방법을 고안하다 생각해낸 것이 정렬이다.

문제를 잘 살펴보면 결국 접두어가 된 다는 것은 앞 숫자가 뒷 숫자의 가장 큰 자리 부터 일부분이 같다는 것으로 해석 가능하고 이를 적용하여 사전에 배열을 오름차순 정렬하였다.

 

시도1

def solution(phone_book):
    answer = True
    
    d = {}
    
    phone_book.sort()
    
    for idx in range(len(phone_book)-1):
        if phone_book[idx] in phone_book[idx+1]:
            answer = False
            break
            
    return answer

 

오류

13번만 오류나서 원인을 찾아보니

- 이전 인덱스의 전화번호가 이후 인덱스의 전화번호 안에 있는지 확인하면 오류
- 접두사인지 확인해야 하기 때문에, 이전 인덱스의 전화번호 길이만큼의 이후 인덱스 문자열과 이전 인덱스 문자열이 같은지 확인하는거로 수정

을 알 수 있었다.

 

접두어를 확인해야 하는 코드를 작성하며 막상 비교 할 때 in으로 비교하여 접두어가 아닌 포함여부를 따진 것..!

 

시도2

def solution(phone_book):
    answer = True
    
    d = {}
    phone_book.sort()
    
    for idx in range(len(phone_book)-1):
        # 수정 부분 : 이전 값이 다음 값의 앞부분-이전값 길이 만큼 같은지 확인
        if phone_book[idx] == phone_book[idx+1][:len(phone_book[idx])]:
            answer = False
            break
            
    return answer

수정 후 잘 작동하였다.

 

결과

사실 한 번호가 다른 번호의 접두어인 경우와 같이 문제에서 해쉬를 암시하는 듯한 뉘앙스가 나와서 해쉬로 접근했는데,

마땅한 풀이 방식이 떠오르지 않았다.

sort 정렬을 하는 것에 효율성 실패가 되지 않을까 싶었는데, 잘 통과되는 걸 보니

이런 문제에서는 sort/loop 조합을 사용하는 것도 나쁘지 않은 선택인 것 같다.