[LV2/해시] 전화번호 목록

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

프로그래머스

 

 

[풀이]

---

처음 풀이

def solution(phone_book):
    
    phone_book.sort()
    for idx, word in enumerate(phone_book):
        for word2 in phone_book[idx + 1:]:
            if word == word2[: len(word)]:
                return False  
    return True

• phone_book을 sorting 한 뒤(문자열 길이)
• 짧은 문자부터 차례대로 다음 인덱스의 문자열을 비교한다.
• 슬라이싱으로 완전 일치하는지를 비교하고,
• 완전 일치할 때 False를 리턴
• 최악의 시간복잡도는 O(n^2)
• 정확도 테스트는 만점이였는데, 효율성 테스트에서 2개가 틀림

 

이후 풀이

def solution(phone_book):
    
    phone_book.sort()
    for idx, word in enumerate(phone_book):
        if idx != len(phone_book) - 1:
            word2 = phone_book[idx + 1]
            if word == word2[: len(word)]:
                return False  
    return True

• sort 메소드에 대한 이해가 필요한 부분
• phone_book = ["11", "1", "1117", "213", "123456789"]일 때,
• 위 리스트를 정렬하면 첫번째 인덱스의 문자 기준으로 정렬이 이뤄진다.
• ["1", "11", "1117", "123456789", "213"] 이렇게 정렬 되는데,
• 따라서 다음 것만 비교하면 될 뿐, 그 이후의 것은 비교할 필요가 없다.
• for 문을 하나 생략하고, 가벼운 조건문 하나를 추가함으로 써
• 최악의 시간복잡도는 O(n)
• 효율성 테스트에 통과 했다.

 

[풀이 후기]

---

• 이 문제가 왜 해시인지는 아직 모르겠다..
• dictionary를 이용해서 풀려고 했지만, 다른 아이디어가 떠오르지 않았다.
• 완전탐색으로 푸는게 조금 더 직관적인 것 같은데, 다음 인덱스를 비교하는 아이디어를 질문목록에서 보지 못했다면, 생각지도 못했을 것 같다.