[python] 프로그래머스 - 해시 level 2

코딩테스트 연습 : 해시 level 2 전화번호 목록

문제 설명

전화번호 목록 문제

앞의 전화번호가 뒤의 전화번호의 접두어가 되면 안된다. (x) -> 어떤 전화번호도 다른 전화번호의 접두어가 되면 안된다.

시도 1 : 딕셔너리를 2개 사용하여 앞, 뒤 요소를 비교

["119", "97674223", "1195524421"] 예제를 사용해서 설명하자면,

앞의 요소 119를 뒤에서부터 차례로 하나씩 늘려가며 hash1 에 값을 저장하고, 뒤의 요소 "97674223"를 앞의 요소 길이만큼 앞에서부터 차례로 하나씩 늘려가며 hash2에 값을 저장한다.

def solution(phone_book):
    answer = True
    for i in range(len(phone_book)-1):
        hash1 = {}
        hash2 = {}
        for j in range(len(phone_book[i])):
            hash1[phone_book[i][j:]] = 0
            hash2[phone_book[i+1][:j+1]] = 0
            # print(hash1)
            # print(hash2)
            # print("-------------------")
        for key1 in list(hash1.keys()):
            if key1 in hash2:
                answer = False
    return answer

시도1 수행 결과 화면

하지만 이렇게 하게되면

수행 결과 화면과 같이 몇몇개가 실패가 드고 

hash 딕셔너리 낭비도 되고 value 값을 둔 의미가 사라져서 수정하였다.

시도 2: 딕셔너리를 1개 사용하여 앞, 뒤 요소를 비교

def solution(phone_book):
    answer = True
    for i in range(len(phone_book)-1):
        hash1 = {}
        for j in range(len(phone_book[i])):
            hash1[phone_book[i][j:]] = 0
            compare = phone_book[i+1][0:len(phone_book[i])-j]
            if compare in hash1:
                answer = False
                break
        if not answer:
            break
    return answer

시도1과 비슷한 방법으로 hash2 딕셔너리를 사용하는 대신, 뒷 요소를 바로 비교할 수 있겠끔하였으나,

시도2 수행 결과 화면

시도1과 똑같은 결과화면이 나왔다.

문제를 잘 못 이해하였다. 핸드폰 번호 리스트의 순서 상관 없이 어떤 전화번호의 접두사가 되는 순간 false가 된다.

 

시도 3: 리스트 사용하기

다른 사람의 풀이를 참고하였다.

def solution(phone_book):
    for i in range(len(phone_book)):
        k1 = len(phone_book[i])
        for j in range(i+1, len(phone_book)):
            k2 = len(phone_book[j])
            if phone_book[i] in phone_book[j][:k1] or phone_book[j] in phone_book[i][:k2] :
                return False
    return True

한 전화번호의 길이만큼 다른 전화번호의 값과 비교하여 동일하면 false를 리턴하도록 하였다.

참고 블로그 : ychae-leah.tistory.com/47

[algorithm] level-2 전화번호 목록 (python)