sort: 백준 18870번 문제

https://www.acmicpc.net/problem/18870

1. 제출

코드

import sys
import heapq

def main():
    N = int(sys.stdin.readline().rstrip())
    n_list = list(map(int, sys.stdin.readline().rstrip().split()))
    n_set = set(n_list)
    
    n_list_sorted = []
    n_dict = dict()
    
    for n in n_set:
        heapq.heappush(n_list_sorted, n)
        
    for i in range(0, len(n_set)):
        x = heapq.heappop(n_list_sorted)
        n_dict[x] = f"{i}"
    
    target = []
    
    for n in n_list:
        target.append(n_dict[n])
    
    answer = " ".join(target)
    
    print(answer)

if __name__ == "__main__":
    main()
        

그런데, 이렇게 하면 아래처럼 결과가 나옴.
159,312 KB
1,320ms

왜냐하면 쓸데없이 추가적인 리스트(n_list_sorted)
를 생성했기 때문이며
heapq 자체에 메모리 오버헤드가 존재하기 때문임.
또한, sorted를 안써서 heapq의 push, pop 연산이 각각 들어가서 시간복잡도 상수가 두배가 되었음.

그래서 아래와 같은 코드가 더 나은 코드이며, 더 pythonic 하다고 할 수 있음.

2. 더 좋은 코드

import sys

def main():
    N = int(sys.stdin.readline().rstrip())
    n_list = list(map(int, sys.stdin.readline().rstrip().split()))
    
    # 복잡도 = O(n logn)
    sorted_unique_n_list = sorted(set(n_list))
    
    # 숫자에 대하여 순위 매기는 사전 생성
    n_dict = {n: str(i) for i, n in enumerate(sorted_unique_n_list)}
    
    # 원본 리스트에 대해 순위를 매기고 출력함. 딕셔너리 거치게 하면 됨.
    
    answer = " ".join(n_dict[n] for n in n_list)
    
    print(answer)

if __name__ == "__main__":
    main()

3. 정리

sorted 쓴다고 드라마틱하게 복잡도가 올라가지는 않는다.

기본 시간복잡도: O(n log n)

• Python의 sorted()는 Timsort 알고리즘을 사용
• Timsort는 병합 정렬(Merge sort)과 삽입 정렬(Insertion sort)을 결합한 하이브리드 정렬 알고리즘임.

공간복잡도: O(n)

• sorted()는 원본 리스트를 변경하지 않고 새로운 정렬된 리스트를 반환하기 때문에 추가 메모리가 필요함.

특수한 경우:

• 이미 정렬된 데이터: O(n)
• 거의 정렬된 데이터: O(n)
• 역순으로 정렬된 데이터: O(n log n)

실제 사용 예시:

numbers = [4, 2, 1, 3, 5]
sorted_numbers = sorted(numbers)  # [1, 2, 3, 4, 5]

# key 함수 사용
words = ['banana', 'apple', 'cherry']
sorted_words = sorted(words, key=len)  # 길이순 정렬: ['apple', 'banana', 'cherry']

추가로 key 함수를 사용할 경우, key 함수의 시간복잡도도 전체 정렬 시간에 영향을 미친다는 점을 고려할 것.