[pgs전화번호목록]Sorted 함수의 특성을 파악하기

프로그래머스 전화번호 목록

Sorted

Sorted 함수는 자료구조를 sorting 할 때 사용할 수 있으며 python 자체적으로 quick sort, merge sort와 유사하게 O(nlogn) 한도에서 정렬이 이뤄지는 것으로 안다.
Key를 지정할 수 있기 때문에 특히 Dictionary에서 value를 기준으로 정렬하고 싶을 때 많이 사용하곤 한다. (key, value)로 나오는 dict.items()를 value를 기준으로 정렬한다는 뜻이다.

sorted(dict.items(), key=lambda x: x[1])

또한, 문자열 정렬 순서를 알아두면 요긴할 것 같다. (특히 이 문제는 그래야 효율성 테스트에 합격하는 듯하다) 만약 startswith()에 걸리는 문자열이 있다면 연속해서 나올 수밖에 없다는 것. 길이와 관계없이 앞 문자열부터 정렬이 되고 따라서 앞 문자열이 동일하다면 뒤에 어떤 것이 붙든지 이어져서 나오게 된다.
이 특성을 활용해서 O(n^2)으로 풀리던 이 문제를 O(n)으로 풀 수 있게 되었다.

Question

Solution

Sorted와 startswith, 두 가지 함수를 활용해서 풀 수 있다. 다만 Solution 1은 효율성(시간) 테스트 3,4번에서 시간초과가 발생하였고 Solution 2는 빠르게 통과하였다. (아래는 Sol 1과 Sol 2의 효율성 테스트 결과)

Solution 1

['119', '1195524421']. 길이가 짧거나 같은 번호가 길이가 긴 번호의 접두어가 될 수 있다. 그 반대는 성립하지 않는다. 따라서 이중 루프를 돌더라도 자신보다 길이가 긴 번호쪽으로만 확인하면 되기 때문에, 길이를 기준으로 sorting한 후에 loop를 돌려보았다.
최악의 경우 O(n(n-1)/2)이 될 수 있으므로 O(n^2)의 복잡도를 갖는다. 다만 접두어가 있는 경우(False인 경우) loop을 다 돌지 않고 훨씬 전에 마무리가 될 확률이 높지만 True인 경우에는 모든 loop을 다 돌아 확인해야할 것이다.

PSEUDO

• 길이가 짧은 순으로 sorting
• for i in range(len()-1):
  for j in range(i+1, len()):
  sort[j]가 sort[i]로 시작하면 return False (startswith)
• return True

def sol_1(p_book):
    sort = list()
    for num in p_book:
        sort.append((num, len(num)))
    sort = sorted(sort, key=lambda x: x[1])

    for i in range(len(sort)-1):
        s = sort[i][0]
        for j in range(i+1, len(sort)):
            if sort[j][0].startswith(s):
                return False
    return True

Solution 2

sorted 함수의 특성을 이용한다. 어떤 문자열 list를 sorted 할 경우, i와 i+1 번째 문자만 비교해보아도 된다. 만약 접두어 관계가 있다면 연속해서 나올 수밖에 없기 때문이다.

PSEUDO

• sorted(phone_book)
• 루프를 한번 돌면서 바로 뒤에 숫자와 비교만 해주면 됨

def sol_2(p_book):
    sort = sorted(p_book)
    for i in range(len(p_book)-1):
        if sort[i+1].startswith(sort[i]):
            return False
    return True

github