[프로그래머스] 전화번호 목록. 정렬 증명과 O(N)풀이

코드

def solution(phone_book):
    book = set(phone_book)
    for num in phone_book:
        for i in range(1,len(num)):
            check = num[:i]
            if(check in book):
                return False
    return True

• 입력:
  • 전화번호 수 1~1,000,000
  • 각 전화번호 길이 1~20

접근

• 만약 모든 숫자에 대해서 서로 비교를 하면 N^2이 나온다. 1e12가 되면서 백준 기준 1만 초 정도 걸릴 것 같다.
• 문제 유형이 해싱이니, 해싱을 이용해야할 것 같은데 각 전화번호의 프리픽스를 해싱하는 것보다는 전화번호 자체를 해싱하면 좋을 것 같다.
• 그럼 해싱한 값을 뭐랑 비교하면 되지? 새로 비교하려는 전화번호를 앞에서 N글자씩 잘라가면서 해싱된 전화번호(프리픽스 모음)중에 그 값이 있는지 보면 될 것 같다.
• 전화번호 길이가 20이고, 해시 접근시간이 O(1)이므로 비교시간은 O(N)*20으로 결국 O(N)이다.
• 같은 전화번호는 없으므로, dictionary를 사용할 필요 없이 바로 set를 쓰면 된다.
• 같은 전화번호가 있었다면 Count 객체를 썼을 것 같고, 여기서 nlargest의 값이 1을 넘었다면 false를 return하도록 하면 된다.

다른 풀이와의 비교

정렬

• 가장 인기많은 풀이가 sort후에 sort하면 prefix일 가능성이 있는 전화번호가 바로 앞쪽에 있을 것이므로 뒷쪽값만 비교하는 방식을 취했다.
• 시간복잡도는 sort가 있어 O(NlogN)이다.
• 이때 logN이 6이므로 O(N)*20보다 작다고 생각할 수도 있지만, 정렬 과정에서 문자 비교가 들어갈 것이므로 사실은 정렬과정에도 문자비교 20만큼의 연산 시간을 곱해야 한다.

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

• ex) 12, 13, 127 번호가 있다면, 12, 127, 13으로 정렬될 것이다.
  • 12와 127 사이에 prefix가 12가 아닌 다른 값이 올 수가 없다.

증명

• 좀 더 일반적으로 증명하자면, 귀류법을 사용할 수 있다.
  • 만약 순서대로 정렬되어 있는 A,B,C가 있는데, A가 B의 접두어가 아니고, A가 C의 접두어인 경우가 있다고 하자.
  • A의 앞자리는 B의 앞자리보다 작아서 A,B순으로 정렬됐을 것이다.
  • A는 B의 접두어가 아니므로 A의 앞자리는 B의 앞자리와 같지 않다.
  • A는 C의 접두어이므로 A앞자리는 C의 앞자리와 같다.
  • A의 앞자리는 B의 앞자리보다 작으므로, C의 앞자리도 B의 앞자리보다 작다.
  • 그렇다면 A,B,C 의 정렬 순서가 잘못되어있는 것이므로 모순이다.
  • 그러므로 A가 B의 접두어가 아니라면 C도 A를 접두어로 가질 수 없다.
  • 순서대로 정렬되어있는경우 A는 B의 앞 n자리보다 작거나 같으므로 A가 B의 접두어가 될 가능성은 있다.
  • 따라서, 앞 뒤 숫자끼리만 비교하면 된다!

기수 정렬

• 흥미로운 풀이

def solution(phone_book, d = 0):
    answer = True
    radix = [[] for _ in range(10)]

    for number in phone_book:
        if d >= len(number):
            return False
        radix[int(number[d])].append(number) 

    for lst in radix:        
        if len(lst) <= 1:
            continue
        else:
            answer &= solution(lst, d+1)
    return answer

• 재귀적으로 기수정렬 해서 비교하고 있다.
• 만약 같은 기수에서 재귀적으로 들어갔을 때 같은 기수내에 자기보다 짧은 번호가 있다면 같은 번호가 있는 것으로 판단한다.
• 이것도 O(N) (*20) 풀이다.
• 정확히는 O(d*(N+k))이다. (d는 전화번호길이, k는 기수로 오는 숫자의 갯수 즉 10)

고찰

• ... 인줄 알았으나.  내 풀이가 sort 보다 효율성 측면에서 더 느렸다.  최대 5배 차이나는 테스트도 있었다.
• 슬라이싱에서 매번 i번 연산을 해서 그런것 같다. 길이가 20인 단어들만 있다면 20이 아니라,  (19*20)/2인  190을 더 곱해야 한다. sort 방법에 비해 대략 10배이다.   슬라이싱 연산이 비교연산보다 좀 더 최적화가 잘 된건지 연산량에 비해서 좀 더 빠르다..