3문제 챌린지
"파이썬 알고리즘 인터뷰"책의 문제들을 하루에 3문제씩 풀어보려고 한다.
6장 문자열 조작
Q4. 가장 흔한 단어(LeetCode 819)
금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표 등) 또한 무시한다.
아이디어
- 금지된 단어를 제외한 나머지 단어들만 남기기
조건) 영어는 소문자로, 단어만 남기기- 리스트 내 단어들의 빈도수 세기
사용한 풀이
✔️ 금지된 단어 제외
이를 시도하던 과정에서,
paragraph = re.sub('[^\w]', ' ', paragraph.lower())위의 구문을 실행하게 되면 특수 문자들이 사라진 부분에도 공백이 추가되므로,
단어 별로 문자열로 나누는 것에 오류가 발생하게 된다.
따라서 책을 참고하여 단어별로 분리하여 문자열에 할당해주었다.
책에서 얻은 아이디어
- 리스트 컴프리헨션, split() 함수
리스트 컴프리헨션: 기존 리스트를 기반으로 새로운 리스트를 만들어내는 구문#기존 아이디어에서 split() 함수 추가 및 리스트 컴프리헨션 생성 words = [word for word in re.sub(r'[^\w]', ' ', paragraph) .lower().split() if word not in banned]위와 같은 구문을 실행시키면, split()으로 공백들이 리스트 형태로 나뉘며 사라지게 된다.
구분된 단어들은 리스트 컴프리헨션(word)에 저장된다.
✔️ 단어 빈도수 세기
sorted(data, key=lambda x: (-data.count(x), data.index(x))이번에도 람다식과 count(), index() 함수들을 사용하여 빈도수대로 정렬하였다.
빈도수가 많은 기준으로 정렬해야 했기 때문에 -data.count(x)를 사용했고,
후순위로는 index 순서를 지정하였다.
정렬 함수:
sort함수는 리스트 자체를 변경하지만,
sorted 함수는 할당해주지 않는 이상 리스트를 변경하지 않는다.
최종 코드 & 제출 결과
책에 나온 풀이
풀이 1: Counter 객체 사용
- Counter 객체: 딕셔너리의 서브클래스
key와 value 형태로 저장되며,
key는 요소, value는 요소의 개수를 의미한다.counts = collections.Counter(words) #가장 흔하게 등장하는 단어의 첫 번째 인덱스 리턴 return counts.most_common(1)[0][0]개수를 담아두는 counts 변수에 defaultdict()를 사용하여 int 기본 값이 자동으로 부여되도록 하였다.
따라서 키 존재 유무를 확인할 필요 없이 즉시 counts[word]+=1을 수행할 수 있다.
가장 많이 등장하는 단어의 값을 most_common(1)로 추출한다.
단, 딕셔너리의 형태로 저장되었기 때문에 [('ball', 2)]와 같이 저장된다.
따라서 인덱스 [0][0]을 추출하여 원하는 값인 'ball'을 얻는다.
Q2. 그룹 애너그램(Leet Code 49)
문자열 배열을 받아 애너그램 단위로 그룹핑하라.
아이디어
- 단어를 스펠링으로 재정렬
사용한 풀이
✔️ 스펠링으로 재정렬:
단어를 비교하기 제일 쉬운 방법은 스펠링으로 재정렬한 뒤, 단어 자체를 비교하는 방법이라고 생각했다.
for word in strs:
sorted(word)위의 구문을 실행할 경우, 'ate'이 정렬되어 [['a','e','t']] 형태가 된다.
따라서 이를 다시 문자열로 만드는 과정이 추가적으로 필요했다.
for word in strs:
"".join(sorted(word))위의 구문을 실행할 경우, join 함수를 통해 각 요소들을 연결지은 뒤 하나의 문자열로 바꿀 수 있다.
책에 나온 풀이
딕셔너리에 추가 후, 개수 비교for word in strs: anagrams["".join(sorted(word))].append(word)스펠링으로 정렬한 값을 키로 하여 딕셔너리에 추가한다.
존재하지 않는 키를 삽입하려고 할 경우, KeyError가 발생하므로 항상 디폴트를 생성해주는 defaultdict()로 선언한다.
최종 코드 & 제출 결과
Q3. 가장 긴 팰린드롬 부분 문자열(LeetCode 5)
가장 긴 팰린드롬 부분 문자열을 출력하라.
시행착오
어려운 문제였기 때문에, 아이디어 자체를 책에서 얻게 되었다.
사용한 풀이
풀이 1. 중앙을 중심으로 확장하는 풀이
✔️ 팰린드롬 판별 및 투 포인터 확장
def expand(left: int, right: int) -> str:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]2칸, 3칸으로 구성된 투 포인터가 슬라이딩 윈도우처럼 계속 앞으로 전진한다.
윈도우 내의 문자열이 팰린드롬인 경우, 정지한 뒤 투 포인터가 점점 확장한다.
판별하는 윈도우를 2칸, 3칸으로 구성한 이유는
팰린드롬이 bb처럼 짝수일 때도 있고, bab처럼 홀수일 경우도 있기 때문이다.
✔️ 예외 처리
if len(s) < 2 or s == s[::-1]:
return s
result = ''문자열의 길이가 2보다 작으면 팰린드롬이 되지 못하고,
문자열이 좌우대칭일 경우 팰린드롬이므로 빠른 처리를 위해 예외처리를 해준다.
✔️ 슬라이딩 윈도우 우측으로 이동
for i in range(len(s)-1):
result = max(result,
expand(i, i+1),
expand(i, i+2),
key=len)expand()로 정의한 중첩 함수에서 홀수, 짝수 2개의 포인터가
팰린드롬 여부를 판별하면서 계속 우측으로 이동한다.
이렇게 판별한 최댓값이 최종 결과가 된다.
새로 배운 개념
- 정규식 문자 필터링 시, 단어 별로 분리하는 방법
- Counter 객체
- join 함수로 배열내 요소 하나의 문자열으로 변환
- 투 포인터
