[북TIL] 파이썬알고리즘인터뷰 6. 문자열 조작

오늘 TIL 3줄 요약

• 깔끔하고 빠른 코드를 위해선 리스트 컴프리헨션, 람다 표현식, 정규식을 잘 다룰줄 알아야 함.

• python의 유용한 메서드는 반드시 기억

• 같은 기능을 필요로 할때, 처리시간이 빠른 방법을 택하려면 결국 메서드 실행 시간을 알아야함.

  • ex- 문자열 슬라이싱 > reverse() > reversed()+join() > for 반복 > while반복 > 재귀(슬라이싱의54배)

   

TIL (Today I Learned) 날짜

• 2022.07.21. THU ~ 07.27 WED

   

오늘 읽은 범위

• 파이썬알고리즘인터뷰 - 6장 문자열조작

   

책에서 기억하고 싶은 내용을 써보세요.

• isalnum() isdigit():숫자 여부인지 판별해준다. 실수나 음수는 판단불가해서 False 반환

  a = "1"
  b = "english"
  a.isalnum() # True
  b.isalnum() # True
  a.isdigit() # True
  b.isdigit() # False
  
  c = 1
  # c는 int 형태이기에 아래 에러를 띄우면서 메소드 사용이 불가하다.
  # AtttributeError:'int' object has no attribute '~'
  c.isalnum() 
  c.isdigit()
  
  

• sort와 람다의 활용

  s = ['2 A', '1 B', '4 C', '1 A']
  # sort()를 쓴다면 앞의 각 요소의 맨 앞 문자로 정렬하기에 ['1 A', '1 B', '2 A', '4 C']로 정렬된다.
  # 뒤의 알파벳을 우선으로 정렬하려면 람다 표현식을 쓰면된다.
  s.sort(key=lambda x: (x.split()[1], x.split()[0])) 
  # 결과 - ['1 A', '2 A', '1 B', '4 C']
  
  # 람다 표현식 없이 sort()로 함수를 선언한다면
  def func(x):
      return x.split()[1], x.split()[0]
  s.sort(key=func)
  

• 퀵정렬은 데이터에 따라 편차가 크다. 병합은 안정적 성능을 보인다.

• 파이썬의 sorted() 에서 쓰이는 팀소트는 '데이터는 대부분 이미 정리되어 있을 것이다'라는 가정에서 출발, 삽입과 병합 정렬을 휴리스틱하게 조합해 사용하는 정렬 알고리즘이다.

  시간복잡도	최선	평균	최악
  퀵	n log n	n log n	n^2
  병합	n log n	n log n	n log n
  팀소트	n	n log n	n log n

   

 

오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요

• 그룹 애너그램의 풀이 원리는 정렬된 값이 같음을 이용하는 것이다. 백준을 풀 때(특히 하노이탑)도 느꼈지만, 결국 문제를 풀어낼 수 있는 핵심 원리를 파악해야 구현도 가능하다는 것이다. 물론 브루트포스와 같이 원리라 부를만한 풀이가 없는 문제들도 잘 파악해야 하겠지만..

   

궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.

 

• 151페이지 <가장 흔한 단어> 의 이해가 어려웠다. 이해한 과정을 기록해본다.

• paragraph = "Bob hit a ball, the hit BALL flew far after it was hit"
  banned = ["hit"]
  
  def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
    	word_f = [word for word in re.sub(r'[^\w]',' ', paragraph)]
      # 정규식에 따라 단어 문자 아닌 문자 공백 치환
      # p = re.sub(r'[^\w]',' ', paragraph) 일 경우
      # 'Bob hit a ball  the hit BALL flew far after it was hit' 을 리턴함
      # 따라서 list는 아래와 같다.
      # ['B', 'o', 'b', ' ', 'h', 'i', 't', ' ', 'a', ' ', 'b', 'a', 'l', 'l', ' ',...]
      
      word_s = [word for word in re.sub(r'[^\w]',' ', paragraph).lower()]
  	 	# word_f 요소 중 대문자->소문자로 변환
  		# ['b', 'o', 'b', ' ', 'h', 'i', 't', ' ', 'a', ...]
                
      word_t = [word for word in re.sub(r'[^\w]',' ', paragraph).lower().split()]
      # re.sub(r'[^\w]',' ', paragraph).lower().split() 의 반환값은
      # ['bob', 'hit', 'a', 'ball', 'the', 'hit', 'ball', 'flew', 'far', 'after', 'it', 'was', 'hit']
      # 따라서 word for ~ 의 iterator가 연산 가능하다.
  
      word = [word for word in re.sub(r'[^\w]',' ', paragraph).lower().split()
                 if word not in banned]
      # 바로 위 리스트에서 banned 의 요소가 제외된다.
      # ['bob', 'a', 'ball', 'the', 'ball', 'flew', 'far', 'after', 'it', 'was']
      
      counts = collections.Counter(words)
      # Counter({'hit': 3, 'ball': 2, 'bob': 1, 'a': 1, 'the': 1, 'flew': 1, 'far': 1, 'after': 1, 'it': 1, 'was': 1}) 객체를 반환
      return counts.most_common(1)[0][0] # collection.most_common(1)은 [('hit', 3)]를 반환)