[프로그래머스] 해시 2. 전화번호 목록

문제

출처: 프로그래머스

---

풀이

처음 보자마자 생각난 방법은 이중포문으로 순회하며 비교하는 것이다.

효율성 테스트 통과 못할거라고 생각했지만 일단 해봄.

def solution(phone_book):
    answer = True
    for i_idx, i in enumerate(phone_book):
        for j_idx in range(i_idx + 1, len(phone_book)):
            if i in phone_book[j_idx]:
                answer = False
                break
    return answer

역시나 통과 못함. 거기다가 정확성도 틀렸다. in이 하위 문자열을 포함하는 것을 찾는다 해서 사용했는데, 아마 접두어뿐만 아니라 내부에 있는 문자열까지도 찾아서 그런 것 같다.

 

다시 시도

def solution(phone_book):
    answer = True
    phone_book = sorted(phone_book, key = len)
    
    for i_idx, i in enumerate(phone_book):
        for j_idx in range(i_idx + 1, len(phone_book)):
            if phone_book[j_idx].find(i) == 0:
                answer = False
                break
    return answer

짧은 것 먼저 오게 정렬하고 in 대신 find를 사용했다. 정확성 test는 모두 통과했고 효율성 테스트는 실패했다. (짧은것 먼저 오게 정렬하지 않으면 두 개의 케이스에서 실패)

 

시간을 어떻게 줄일 수 있을지 고민하다 지난번 문제인 가장 큰 수에서 문자열을 아스키코드 기준으로 sort했던 것이 생각났다.

len을 key로 사용하지 않고 그냥 정렬하면 아스키코드 순서대로 정렬될 것이고 포문을 두 번 돌릴 필요 없이 바로 다음 문자열과 비교하면 될 것 같았다.

def solution(phone_book):
    answer = True
    phone_book = sorted(phone_book)
    
    for i in range(0, len(phone_book) - 1):
        if phone_book[i + 1].find(phone_book[i]) == 0:
            answer = False
            return answer
            
    return answer

통과됐긴 한데 이게 해시를 사용한게 아니어서 이래도 되나 싶다.

---

다른 사람의 풀이

나는 해시를 사용하지 않아서 다른 사람의 풀이를 확인했다. 나와 비슷한 원리로 푼 사람이 있기도 하고 해시를 사용한 사람도 있어 본래 목적에 맞게 푼 사람의 풀이를 가져왔다.

def solution(phone_book):
    answer = True
    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 and temp != phone_number:
                answer = False
    return answer

그런데 이중포문을 사용했다. 아마 처음 내 코드가 통과하지 못한 이유는 이중포문에 find()까지 사용해서 그런 듯 하다.

이 분 코드의 테스트 결과이다.