[Python Algorithm] 문자열

본 포스팅은 책 '파이썬 알고리즘 인터뷰'를 공부하며 정리한 내용입니다.

아래 내용은 ch6의 내용을 참고하였습니다.

그렇다면.. 파이썬 알고리즘 레츠고~

Char

• char.isalnum() : 영문자, 숫자 여부 판별

• char.lower() : 소문자 변환

• char1 != char2 : 대소문자 구분함 ('a' == 'A' 의 값은 false)

String

• char처럼 str.lower() 사용 가능

• Slicing -> 내부적으로 c로 구현돼있어서 빠름

  my_string = "Hello, World!"
  
  # Basic slicing
  substring1 = my_string[7:12]  # Extracts "World"
  
  # Omitting start or stop
  substring2 = my_string[:5]    # Extracts "Hello"
  substring3 = my_string[7:]    # Extracts "World!"
  
  # Using negative indices
  substring4 = my_string[-6:-1]  # Extracts "World"
  
  # Using step
  substring5 = my_string[::2]    # Extracts "Hlo ol!"
  
  # Reverse the string
  substring6 = my_string[::-1]   # Reverses the entire string

• str.split() : 공백

  • 눈물이 앞을 가린다.. 나는 왜 그동안 c++로 알고리즘을 했을까..? 맨날 코테 전에 vector로 string split 하는 함수 눈으로 슥 보고 들어갔는데... 아........ python에서 이게 이렇게 쉽다니.......

  # 공백을 기준으로 문자열을 나누기
  sentence = "Hello, world! How are you?"
  words = sentence.split()
  print(words)
  # 출력: ['Hello,', 'world!', 'How', 'are', 'you?']
  
  # 최대 분할 횟수를 지정하여 나누기
  data = "apple,banana,orange,grape"
  fruits = data.split(',', maxsplit=2)
  print(fruits)
  # 출력: ['apple', 'banana', 'orange,grape']
  

• str.isdigit() : 숫자인지 검사

List

• 선언

  letters, digits = [], []
  empty_list = list()
  numbers = [1, 2, 3, 4, 5]
  numbers = list(range(1, 6))
  squares = [x**2 for x in range(1, 6)]
  repeated_list = [0] * 5

• pop() : list의 마지막 값을 pop하며 O(1)

• pop(n) : list의 indext 위치(n)에 있는 값을 pop 하며 O(n) 가능

  • pop(1) : 1번째 idx
  • pop(-1) : 마지막 idx

• 뒤집기

  • list.reverse()
  • list = list[::-1]
  • list[:] = list[::-1]

• list.index(dummy) : dummy의 index가 뭔지 가져오는 함수임

• list[idx] : idx의 값을 가져옴

• + 연산자 활용 가능

  a = [1,2,3]
  b = [4,5,6]
  a+b # [1,2,3,4,5,6]
  b+a # [4,5,6,1,2,3]

• sort

  • 제자리에서(in-place) 정렬하며, 새로운 리스트를 만들지 않음
  • 오름차순(ascending order)이 defualt
  • 내림차순(descending order)으로 정렬하려면 reverse=True 옵션을 사용할 수 있습니다.
  • 최악의 경우 O(n log n)

  numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
  
  # 오름차순 정렬
  numbers.sort()
  print(numbers)
  # 출력: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
  
  # 내림차순 정렬
  numbers.sort(reverse=True)
  print(numbers)
  # 출력: [9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1]

• sorted() 함수:

  • 새로운 정렬된 리스트를 반환합니다. 원본 리스트는 변경되지 않습니다.
  • 최악의 경우 O(n log n)

  numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
  
  # 오름차순 정렬된 새 리스트 생성
  sorted_numbers = sorted(numbers)
  print(sorted_numbers)
  # 출력: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
  
  # 원본 리스트는 변화 없음
  print(numbers)
  # 출력: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

• key 매개변수:

  sort() 메서드와 sorted() 함수는 key 매개변수를 사용하여 정렬 기준을 지정할 수 있습니다.

  예를 들어, 문자열의 길이를 기준으로 정렬하거나 특정 함수의 결과에 따라 정렬할 수 있습니다.

  words = ["apple", "banana", "kiwi", "orange", "strawberry"]
  
  # 문자열의 길이를 기준으로 정렬
  words.sort(key=len)
  print(words)
  # 출력: ['kiwi', 'apple', 'banana', 'orange', 'strawberry']

• key + lambda 함께 활용하기

  letters = ["let1 art can", "let2 own kit dig"]
  letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))
  # 두 개의 키를 람다 표현식으로 정렬
  # 첫번째 비교 기준 : 먼저 "art can","own kit dig"를 비교하는것
  # 두번째 비교 기준 : 첫번째 비교 값이 동일하다면, "let1", "let2"

Deque

• 선언 방식

  # 1. collections 활용 
  from collections import deque
  
  strs = deque()
  
  # 2. typing과 collections 활용
  import collections
  from typing import Deque
  
  strs: Deque = collections.deque()

• pop(), popLeft() : 둘 다 O(1)

• pop()의 시간 복잡도를 살펴보았을 때, 수정이 빈번한 경우에는 list보다 deque가 유리하다

  • list는 fixed size memory block으로 구성돼서 원소의 추가 삭제에 따라 list의 전체 원소의 이동이 일어나서 O(n)
  • deqeu의 경우에는 double linked list로 구성되어 있어서 O(1)

• 그렇다면 deque의 단점은 무엇인가? 바로 특정 원소에 접근할 때이다.

  • double linked list에서 눈치를 챘을 수 도 있지만, linked list 특성상 특정 원소에 접근하기 위해서는 iteration을 돌아야 하기때문이다

• 결론 : 삽입/삭제가 빈번할 때는 deque, 조회가 주로 일어날 때에는 list를 활용하는것이 맞다