[문제풀이] Hash - 전화번호 목록

 

 

1차 시도

---

def solution(phone_book):
    phone_book.sort()
    # 어차피 길이가 같으면 절대 있을수 없지
    phone_dict = {}
    for phone in phone_book:
        phone_dict[len(phone)] = phone
    if len(set(list(phone_dict.keys()))) == 1:
        return True

    for i in range(len(phone_book)):
        for j in range(1, len(phone_book)):
            if phone_book[i+j].startswith(phone_book[i]) or phone_book[i].startswith(phone_book[i+j]):
                return False
        del phone_book[i]
    return True

첫번째 시도는 당연하게 쌉망했다. 문제가 hash로 분류되어있어서 dictionary로 어떻게 해결하면 좋을까 고민해봤는데, 도저히 해결 방법이 떠오르지 않았고 그냥 딱 len(set(list(~~~ 이 부분만 dictionary를 사용해서 검사하는 것 밖에 생각이 나지 않았다. 문제에서 '중복된 전화번호는 없다'라는 부분이 있는데, 그렇다면 전화번호의 길이가 모두다 같다면 절대 접두어가 있을 수 없기 때문에 그 부분을 캐치해주는 코드이다. 그리고 나머지 제한사항에 대해서는 리스트 특성을 사용하였다. 그런데 효율성과 몇가지 테스트케이스에서 통과를 못했다. 사실 여기서 중첩 반복문을 사용한 것이 정말 지저분하게 느껴졌다.

 

그래서 좀 고민해보니까 처음에 정렬했을때는 '정렬하면 접두어가 대충 몰리니까 빨리 끝나겠군' 이정도였는데, 펜으로 끄적이다보니 어? 그러면 당연히 짧은게 앞에 오지 않나? 해서 당장 중첩 반복문을 집어던지고 1차원의 반복문으로 바꿔서 다시 돌려벼렀다.

 

 

2차시도

---

def solution(phone_book):
    phone_book.sort()
    # 어차피 길이가 같으면 절대 있을수 없지
    # 어차피 정렬하면 짧은게 먼저오지 않나?
    phone_dict = {}
    for phone in phone_book:
        phone_dict[len(phone)] = phone
    if len(set(list(phone_dict.keys()))) == 1:
        return True
    for i in range(len(phone_book)-1):
        if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
            return False
    return True

성공하였다. 문제 다 풀고 다른사람 풀이를 바로 보여줘서 좀 봤는데, startswith를 사용했더라. zip과 함께. zip은 내가 평소에 코드짤때도 엄청 많이 쓰던 것이었는데 왜 쓰질 못하니....

 

 

의문점

---

이 문제 도대체 hash로 어떻게 푸는 건지 모르겠다. 그냥 리스트로 풀었다. 혹시 hash로 푸는 방법을 설명해줄 능력자...?

 

 

Reference

---

https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록