문자열 정렬하기(1)

문제

 

 

내 풀이

 

# 분석

• 시간 복잡도 : 
  • for word in my_string : my_string의 길이를 N이라 하면, 문자열의 각 문자를 한 번씩 확인하므로 O(N)
  • if "0" <= word <= "9": answer.append(int(word)) : 숫자인지 확인하는 조건문과 리스트에 추가하는 작업은 O(1)
  • answer.sort() : 정렬 알고리즘은 O(K log K) (단, K는 answer 리스트의 크기, 최대 N)
  • 최종 : O(N) + O(1) + O(N log N) = O(N log N)
• 공간 복잡도 :
  • my_string (입력 문자열) : 입력 자체는 별도의 공간을 추가로 사용하지 않으므로 O(1)
  • answer (숫자 리스트) : 숫자 개수를 최대 N개 저장할 수 있음 O(N)
  • 정렬 시 추가 공간 : sort()는 Python의 Timsort를 사용하며 O(K) ~ O(K log K) 추가 공간 사용 가능
  • O(1) + O(N)  = O(N) 

 

 

# 최적화

def solution(my_string):
    return sorted([int(word) for word in my_string if word.isdigit()])

 

 

• 시간 복잡도
  • 문자열 순회 및 숫자 판별 (isdigit())
    • my_string의 길이가 N일 때, 한 번 순회하면서 숫자 판별 → O(N)
  • 정렬 (sorted())
    • 리스트에 포함된 숫자 개수를 K라 하면, 정렬 복잡도는 O(K log K)
    • 최악의 경우 K=N, 따라서 O(N log N)
  • 결과 : O(N) + O(N log N) = O(N log N)

 

• 공간 복잡도
  • 숫자 리스트 저장(if word.isdigit())
    • 리스트 컴프리헨션을 사용하지만 시간복잡도에 영향은 없다. O(K) (최대 O(N))
  • 정렬 과정 추가 공간(sorted())
    • Python의 sorted()는 **Timsort (O(K))**의 추가 공간을 사용
    • 최악의 경우 K=N → O(N) 추가 공간 필요
  • 결과 : O(N) + O(N) 

 

 

 

 

# 정리

※ 컴프리헨션 : 리스트, 집합, 딕셔너리, 조건문 등을 간결하게 만드는 Python 문법이다.

※ isdigit() : 0~9의 숫자로만 이루어진 문자열에 대해서만 True를 반환한다.

※ sorted() : 리스트, 문자열, 튜플 등 반복 가능한(iterable) 객체를 정렬하여 새로운 정렬된 리스트를 반환하는 내장 함수이다.

 

• 원본 데이터를 변경하지 않고 정렬된 새로운 리스트를 반환 (원본 유지)
• 기본적으로 오름차순 정렬 (ascending order)
• reverse=True 옵션을 주면 내림차순 정렬 (descending order) 가능
• key 매개변수를 활용하여 다양한 기준으로 정렬 가능