[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
Author And Source
이 문제에 관하여([pgs전화번호목록]Sorted 함수의 특성을 파악하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jonas-jun/pgs-phonenum저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)