99클럽 코테 스터디 5일차 TIL + 전화번호 목록

오늘의 학습 키워드: sort, startswith

문제: 전화번호 목록

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

프로그래머스

 

풀이

1. 딕셔너리(Hash)를 이용한 풀이

def solution(phoneBook):
    table = {}

    for number in phoneBook:
        table[number] = True

    for number in phoneBook:
        for i in range(1, len(number)):
            prefix = number[:i]
            if prefix in table:
                return False

    return True

 

이중 for문으로 풀면 안될것 같지만? 문제의 효율성 테스트는 이를 허용합니다.

이게 가능한 이유는

phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.

 

전화번호의 길이가 1~20 이기 때문입니다.

또한 prefix가 테이블에 있는지 확인하는 부분에서 테이블이 딕셔너리이기 때문에 O(1)의 시간복잡도를 갖습니다.

따라서 전체 시간복잡도는 O(n*m)이 된다고 할 수 있습니다.

 

2. sort(), startswith() 내장함수 사용하기

sort를 이용하면 반복문을 1회만 돌리고도 판별이 가능합니다. 이게 가능한 이유는 숫자가 아니라 문자열이기 때문입니다.

 

문제의 예시인 ["12","123","1235","567","88"] 를 보겠습니다.

만약 자료형이 INT였다면 결과는 [12,88,123,567,1235] 일 것입니다.

그러나 문자열이기 때문에 ['12', '123', '1235', '567', '88']라는 결과를 받을 수 있습니다.

 

그렇다면 바로 앞의 값과의 비교만 진행하면 문제는 쉽게 해결될 것입니다.

이를 위해 startswith() 함수를 사용해줍니다.

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
                return False
    return True

 

그럼 시간복잡도는 어떻게 될까요?

우선 반복문을 돌렸으니 O(n)은 기본일 것입니다. 그렇다면 sort()는 어떤 시간복잡도를 지닐까요?

GPT를 활용하여 이에 대한 답을 찾아냈습니다.

---

리스트를 정렬한 후 반복문을 돌리는 경우, 정렬의 시간 복잡도와 반복문의 시간 복잡도를 합산합니다.

1. 정렬: Python의 sort() 함수는 Timsort 알고리즘을 사용하며, 최악의 경우 시간 복잡도는 O(nlog⁡n)입니다.
2. 반복문: 정렬된 리스트를 순회하는 반복문의 시간 복잡도는 O(n)입니다.

따라서, 정렬 후 반복문을 돌리는 전체 시간 복잡도는 다음과 같습니다: O(nlog⁡n)+ O(n) = O(nlogn)

---

 

실은 문제를 풀면서 단순하게 중첩 반복문을 사용해봤는데 효율성 3,4번에서 통과가 되지 않는 이유가 궁금했는데 이 때문인듯 합니다.

 

그럼 추가로 Timsort 알고리즘에 대해서 간단하게 알아보겠습니다.

 

Timsort는 2002년 파이썬의 리스트 정렬을 위해 팀 피터스(Tim Peters)가 개발한 정렬 알고리즘입니다. Timsort는 실제 데이터의 정렬 성능을 최적화하기 위해 합병 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)의 장점을 결합한 하이브리드 정렬 알고리즘입니다.

'실제 데이터는 대부분 이미 정렬돼 있을 것이다' 라는 가정에 기반한 정렬 알고리즘이라고 합니다.

 

Timsort는 다음과 같은 단계로 작동합니다:

1. 런(Run) 생성: Timsort는 데이터 리스트를 작은 정렬된 하위 리스트(run)로 나눕니다. 각 run은 최소 크기(minimum run size)를 가지며, 기본적으로는 32 또는 64로 설정됩니다. Timsort는 리스트를 순회하며 이미 정렬된 부분(run)을 식별하고, 정렬되지 않은 부분은 삽입 정렬을 사용하여 정렬합니다.
2. 런 병합: 생성된 run들을 합병 정렬을 사용해 병합합니다. 병합 과정에서는 각 run의 크기를 비교하고, 작은 run부터 병합하여 최종적으로 전체 리스트를 정렬합니다.

최악의 시간복잡도는 O(nlogn)입니다.

참고: https://questionet.tistory.com/61

파이썬의 정렬 알고리즘 Timsort (삽입정렬 + 병합정렬)

 

(알고리즘은 추가로 포스팅 하겠습니다..)

 

회고

시간 복잡도를 생각하다 정렬 알고리즘까지 가버렸습니다.. 한번 정리해보는 시간을 가질 필요가 있어보입니다.

 

내일 학습할 것.

Timsort, SQL