개발/북TIL

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

대왕판다 2022. 7. 27. 19:08

오늘 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 nn log nn^2
    병합n log nn log nn log n
    팀소트nn log nn 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)]를 반환)