[Programmers] 전화번호 목록 (with Python / 해시테이블)

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=python3

프로그래머스

문제설명

문제 설명

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

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

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

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

 

문제풀이

 

 나의 아이디어
 번호의 길이가 다른데, 짧은번호가 배열의 앞에와야 유리한데..
 0번째 인덱스값과 그 나머지값을 비교하는 방식으로 늘려나가면서 검사?

 1. 배열을 받아서 각 문자열 값을 숫자로 변환한후 오름차순 정렬

변환하는 과정중에 

for item in arr:

   item = int(item) 으로 하니 배열값이 갱신이 안되어

 

for i in range()를 사용했다.

근데 나중에보니 오름차순 정렬을 문자열 상태일 때 해도 된다는걸 잊고있었다....

 

결국 정렬 후 감이 잘 안와서, 해시테이블을 쓰기로 했다.

 

구현할 로직

1. 폰북 배열 속 원소를 key로 하는 myDict 키,값 생성.
2. 폰북 속을 탐색하며 item 마다 각 item의 문자를 부분문자열로 하는 부분문자열 생성.
3. 그리고 그 부분 문자열이 myDict의 key로 속해있는지 검사
4. + 자기자신이 아닌지 검사
5. 조건문 하나라도 충족하면 False값 반환

 

 

코드

def solution(phone_book):
    answer = True
    myDict =  {}
    
    for item in phone_book:
        myDict[item] = 1

    for item in phone_book:
        part = ""
        for num in item:
            part += num # 문자를 더해가며 부분문자열 생성
            if part in myDict and part != item:
                return False
    # 1. 폰북 배열 속 원소를 key로 하는 myDict 키,값 생성.
    # 2. 폰북 속을 탐색하며 item 마다 각 item의 문자를 부분문자열로 하는 부분문자열 생성.
    # 3. 그리고 그 부분 문자열이 myDict의 key로 속해있는지 검사
    # 4. 자기자신이 아닌지 검사
    # 5. 조건문 하나라도 충족하면 False값 반환
    return answer