[프로그래머스][코딩연습/해쉬]전화번호 목록

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 이하입니다.

---

안보고 끝까지 풀어보자 싶어서.. 오래 걸렸지만 내 생각대로 품..

import numpy as np

def solution(phone_book):
    array = np.array([[None] * 20] * len(phone_book))

    for i in range(len(phone_book)):  # 2차원 배열에 저장
        L = list(phone_book[i])
        array[i, :len(L)] = L

    for j in range(20):
        A = array[:, j]
        for i in range(len(phone_book)):
            if (A[i] == None) & (array[i,j-1] != None):
                B = array[i, 0:j]
                print(B)
                for k in range(len(phone_book)):
                    if (np.array_equal(array[k, 0:j], B)) & (k != i):
                        return False
    return True

내가 푼 방법은 전화번호부 길이 * 최대번호길이 인 2차원 배열을 만들어서

번호를 저장하고, 빈 부분은 None으로 저장함..

그리고.. 텍스트로 설명하긴 어려운데.. 난 그림 그리면서 풀었다. 쨌든 진짜 복잡하게 생각해서 풀었는데 돌아가긴 하더라

 

그러고 나서 검색해보니 길이 순서대로 sorting하는 내장함수가 있더라(몰랐다)

list.sort(key=len)

다시 푼다면 길이순으로 배열을 sorting 한 후에 길이별로 끊어서 찾고자하는 요소 뒤에 부터 for문 돌려서 같은거 찾을 듯.. 이렇게하면 빨리 풀 수 있을 것 같다. 근데 이제 문제에 지겨워 져서 다시 시도하고 싶지 않다..ㅋㅋㅋ

 

 

쨌든 문제의 취지에 맞게 hash로 푼 답을 찾아봤다. 프로그래머스는 이래서 좋다. 백준은 적절한 모범답안 찾기가 어려움..

 

def solution(phone_book):
    hash_map={}
    for phone_number in phone_book:
        hash_map[phone_number] = 1

    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if (temp in hash_map) & (temp != phone_number):
                return False
    return True

처음에 이렇게 푼 사람 똑똑하다고 인정한다.

이해하고 다시 안보고 쳐보았다. hash_map의 key로 전화번호를 저장해 놓고

전화번호가 1123면

1이 hash_map 의 키 중에 있는지

11이 hash_map 의 키 중에 있는지

112이 hash_map 의 키 중에 있는지 

113이 hash_map 의 키 중에 있는지 확인하고

있다면 그게 자기 자신이 아닌지 확인하고

False로 출력

 

똑똑하군..