[Book Review] Python Algorithm Interview (3)

Tony Kim·2021년 10월 6일
[Book Review] Python Algorithm Interview
0

[Book Review] Python Algorithm Interview

목록 보기
3/5
post-thumbnail

[Book Review] Python Algorithm Interview (3) : 문자열 조작

1. 문자열 조작

문자열 조작
문자열을 번경하거나 분리하는 여러과정

사용분야
1) 정보처리분야 (웹페이지 탐색 시 문자열 처리 어플맄이션 이용)
2) 통신시스템분야 (데이터 전송)
3) 프로그래밍시스템분야 (컴파일러나 인터프리터 등이 문자열 해석/처리 -> 기계어로 변환, 이때 매우 정교한 문자열 처리 알고리즘 사용

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q1. Palindrome (팰린드롬, 회문)

1) 리스트로 반환

def isPalindrome(self, s:str) -> bool:
  strs = []
  for char in s:
    if char.isalnum(): //영문자, 숫자 여부 판별 -> 해당 문자만 추가
      strs.append(char.lower())
  while len(strs) > 1:
    if strs.pop(0) != strs.pop():
      return False
ㅤ
  return True

2) Deque자료형 활용

deque?

• deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
• deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
• deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
• deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
• deque.remove(item): item을 데크에서 찾아 삭제한다.
• deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).
def isPalindrome(self, s:str) -> bool:
  strs : Deque = collections.deque()
ㅤ
  for char in s:
    if char.isalnum():
    strs.append(char.lower())
ㅤ
  while len(strs) > 1:
    if strs.popleft() != strs.pop():
     return False
ㅤ
  return True
->pop(0)은 O(n)이지만 popleft()가 O(1)이기 때문에 성능차이

3) 슬라이싱 사용

def isPalindrome(self, s:str) -> bool:
s= s.lower()
s = re.sub(‘[^a-z0-9]’, ‘’, s)
return s == s[::-1]

문자열 슬라이싱
-> 매우 빠르게 동작
-> 위치 지정하면 해당 위치의 배열포인터 얻게되며 이를 통해 연결된 객체를 찾아 실제 값을 찾아내는데 이 과정이 매우 빠름
-> 문자열 조작할 때는 슬라이싱이 빠름

0    1    2    3   4
안   녕   하   세   요
-5  -4   -3  -2   -1
S[1:4 ] 녕하세
S[1:-2] 녕하 
S[1: ] 녕하세요 
S[ : ] 안녕하세요 (사본리턴, 파이썬은 a=b 값할당이 아닌 참조형태)
S[1:100] 녕하세요 
S[-1] : 요 
S[-4] 녕 
S[:-3] 안녕 
S[-3: ] 하세요 
S[::1] 안녕하세요  
S[::-1 ] 요세하녕안 
S[::2 ] 안하요 (2칸씩 오른쪽으로 이동하며 참조)

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q2. 문자열 뒤집기

1) 투포인터 이용

def reverseString(self, s:List[str]) -> None:
  left, right = 0, len(s) – 1
  while left < right:
    s[left], s[right] = s[right], s[left]
    left +=1
    right -=1

2) 파이썬다운 방식

def reverseString(self, s: List[str]) -> None:
  s.reverse()
문자열 슬라이싱은 오류 발생가능하다고함..

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q3. 로그파일 재정렬

Q. 로그를 재정렬

  • 로그의 가장 앞부분은 식별자
  • 문자로 구성된 로그가 숫자로그보다 앞에온다
  • 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다
  • 숫자 로그는 입력 순서대로 한다

입력

logs = [“dig1 8 1 5 1”, “let1 art can”, “dig2 3 6”, “let2 own kit dig”, “let3 art zero”]

출력

[“let1 art can”, “let3 art zero”, “let2 own kit dig”, “dig1 8 1 5 1”, “dig2 3 6]

풀이

def reorderLogFiles(self, logs: List[str]) -> List[str] :
  letters, digits = [], []
  for log in logs
    if log.spilt() [1].isdigit():
      digits.append(log)
    else
      letters.append(log)
      ㅤ
  #2개의 키를 람다 표현식으로 정렬
  letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))
  return letters + digits

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q4. 가장 흔한단어

Q. 금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력
대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표 등) 또한 무시

입력

paragraph = “Bob hit a ball, the hit BALL flew far after it was hit.”
banned = [“hit]

출력

“ball”

풀이 a)

대소문자 + 쉼표가 있기 때문에 data cleansing 필요
(입력값에 대한 전처리= preprocessing 필요)

words = [word for word in re.sub(r’[^\w]’, ‘ ’, paragraph) 
// ^ = not, w = word character 
// 단어문자가 아닌 모든 문자 공백치환
.lower().split()  
// 소문자화 + 공백으로 분리
if word not in banned] 
// banned에 있는 word가 아니라면

풀이 b) 

counts = collections.defaultdict(int)
// 자동으로 딕셔너리 value 생성
for word in words:
  count[word] += 1
return max(counts, key=counts.get)

풀이 c) 

counts = collections.Counter(words) 
return counts.most_common(1) [0][0]

완성된 풀이

import collections
import re
from typing import List
ㅤ
class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        words = [word for word in re.sub(r'[^\w]', ' ', paragraph)
            .lower().split()
                 if word not in banned]
ㅤ
        counts = collections.Counter(words)
        # 가장 흔하게 등장하는 단어의 첫 번째 인덱스 리턴
        return counts.most_common(1)[0][0]

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q5. 그룹 애너그램

Q. 문자열 배열을 받아 애너그램 단위로 그룹핑

입력

[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

출력

[
  [“ate”, “eat”, “tea”]
  [“nat”, “tan”]
  [“bat”]
]

풀이

def groupAnagrams(self, strs: List[str] ) -> List[List[str]]:
  anagrams = collections.defaultdict(list)
ㅤ
  for wor in strs:
    anagrams[‘ ‘.join(sorted(word))].append(word) 
    // ‘ ‘ 공백은 뒤에 붙는거
ㅤ
  return list(anagrams.Values())

sorted / sort / join

b = ‘zds’
sorted(b) = [‘d’, ‘s’, ‘z’]
“”.join(sorted(b)) = ‘dsz’
ㅤ
sorted와 다른 sort()함수는 리턴갑이 None이므로 주의
sorted 정렬을 위한 키 또는 함수 지정 가능
ㅤ
stirng = [~]
sorted(string, key=len)

or

def fn(s):
  return s[0], s[-1]  // 첫문자열과 마지막 문자열 순으로 정렬
ㅤ
sorted(string, key=fn)

or

람다
sorted(a, key = lambda s: (s[0], s[-1]))

자바 병합정렬 (하지만 팀정렬 포팅 시작)
파이썬 팀정렬 (이미 정렬되어있는 경우 비교를 건너뜀)

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

Q6. 가장 긴 팰린드롬 부분 문자열

Q. 가장 긴 팰린드롬 부분 문자열 출력

입력

“babad”

출력

“bab”

다이나믹 프로그래밍으로 풀 수도 있음
(여기선 직관적이지 않고 실행속도가 늦음)

여기서는 투포인터가 중앙을 중심으로 확장하는 형태로 풀이

def longestPalindrome(self, s: str) -> str:
  # 팰린드롬 판별 및 투 포인터 확장
  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]
ㅤ  ㅤ
  # 해당 사항이 없을때 빠르게 리턴   
  // 그 자체가 팰린드롬인 경우 (길이 한글자 or 역순 동일)
  if len(s) < 2 or s == s[::-1]:   
    return s
ㅤ   
  result = ''
  # 슬라이딩 윈도우 우측으로 이동
  for i in range(len(s) - 1):
    result = max(result,
                 expand(i, i + 1),
                 expand(i, i + 2),
                 key=len)
    return result

유니코드와 UTF-8

초기 : 아스키코드 : 1바이트에 모든 문자 표현 (깨지거나 했음)

유니코드
2~4바이트 공간에 여유있게 문자 할당
하지만 영문자도 3바이트 이상 공간 사용 -> 메모리 낭비

UTF-8
가변길이 문자 인코딩 방식으로 효율적으로 인코딩하는 대표적인 방식
유니코드 값에 따라 가변적으로 바이트를 결정하여 불필요한 공간낭비 절약가능
(파이썬이 사용하는 건 아님)

profile
Tony Kim
Back-end-dev
이전 포스트

[Book Review] Python Algorithm Interview (2)

다음 포스트

[Book Review] Python Algorithm Interview (4)

0개의 댓글