🧩 코딩 테스트 정복기 @21#B*06

파이썬 알고리즘 인터뷰

📚📚📚👈🏻 책 구매 링크

🤴🏻👸🏻👵🏻👴🏻 👈🏻 소스코드 깃허브

😥😱🤪👈🏻   책 정오표   

🏓📡📺  👈🏻   유투브 채널

---

문자열 조작 String Manipulation

문자열을 변경, 분리하는 등의 여러 과정을 말한다.

코테에서도 문자열 조작은 매우 빈번하게 출제되는 주제 중 하나이다. 

특히 실무에서도 다양한 분야에 쓰이는 상당히 실용적인 주제이다.

 

문자열 처리와 관련한 알고리즘이 쓰이는 대표적인 분야. 

1. 정보처리 분야 :

키워드 탐색 시, 문자열 처리 앱을 이용하게 된다.

특히 현대의 거의 모든 정보는 문자열로 구성되어 있으며

문자열 처리는 정보처리에 핵심이다. 

 

2. 통신시스템 분야:

데이터 전송에서 문자열 처리는 매우 중요하다. 문자, 이메일 등에 기본적으로 사용된다. 

 

3. 프로그래밍 시스템 분야:

프로그램은 그 자체가 문자열로 구성, 문자열에 매우 정교한 처리 알고리즘이 쓰인다. 

---

회문 Palindrome 

리스트와 데크를 사용하면,

def isPalindrome(self, s:str) -> bool:
	strs = []
  for char in s:
    	if char.isalnum():
        	strs.append(char.lower())

  whie len(strs) > 1 :
    	if strs.pop(0) != strs.pop():
        	return False
  	return True

isalnum() 메서드 : 영문자, 숫자 여부를 판별하는 함수 

lower() 메서드 : 문자들 모두 소문자로 변환하는 함수

 

여기서 데크 ( Deque) 를 사용하면 더 빠르게 처리가 가능하다.

pop(0) 대신 popleft() 를 사용하는 것이 더 빠르다.

---

슬라이싱을 사용하면, 

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

[::-1] 문자열에 이 문구를 붙이면 뒤집어서 볼 수 있다. 

 

 

🎊🤩

파이썬에서는 문자열 슬라이싱이라는 매우 편리한 기능을 제공한다.

심지어 내부적으로도 매우 빠르게 돌아가니 잘 활용하는 것이 좋다. 

 

S[:] = 안녕하세요

S[1:] = 녕하세요

S[1:-2] = 녕하

S[:-3] = 안녕

S[-3:] = 하세요

S[::-1] = 요세하녕안S[::2] = 안하요 ( 2칸씩 앞으로 이동)

S[1:100] = 녕하세요 (인덱스 넘치면 최대 길이만큼표현됨) == S[1:] 

---

문자열 뒤집기 

reverse() 함수 활용

s.reverse() 는 s[::-1]  과 같이 해당 문자열을 거꾸로 뒤집어주는 함수이다. 

s[:] = s[::-1]
s = s[::-1] # 이것이 안되는 경우도 있는데, 안되면, 위의 방법으로 하면된다. 
# ['a', 'b', 'c'] => ['c', 'b',  'a']

 

투 포인터를 이용한 뒤집기Two pointer 

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

---

로그파일 재정렬

Lambda 와 + 연산자 활용

여러가지 조건으로 집합, 수열등을 정렬 해야 할때, 람다를 활용하면 편하다. 

 

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

def reorderLogFiles(self, logs: List[str]) -> List[str]:
	letters, digits = [], []
    for log in logs:
    	if log.split()[1].isdigit():
        	digits.append(log)
        else:
        	letters.append(log)

	letters.sort(key= lambda x: (x.split()[1:], x.split()[0]))
	return letters+digits

😁Lamda 표현식

람다 표현식이란 식별자 없이 실행 가능한 함수를 말한다. 

함수 선언이 따로 없어도 하나의 식으로 함수를 단순하게 표현이 가능하다. 

 

List Comprehension 이 람다표현식보다 훨씬 간단하고 가독성도 좋아서 람다보다 많이 쓰인다. 

# 람다표현을 통해 정렬하는 경우

s = ['2 a', '1 b', '4 c', '1 a']
# 맨 앞의 숫자 인자를 기분으로 정렬이 된다.
print(sorted(s))  # ['1 a', '1 b', '2 a', '4 c']

# 숫자가 아니라 뒤의 알파벳을 기준으로 정렬을 하기 위해서
s.sort(key=lambda x: (x.split()[1], x.split()[0]))
print(s)  # ['1 a', '2 a', '1 b', '4 c']


def sorting(x):  # 따로 함수를 선언해서 사용도 가능하다. 모듈화 가능.
    return x.split()[1], x.split()[0]


s.sort(key=sorting)
print(s)  # ['1 a', '2 a', '1 b', '4 c']

---

가장 흔한 단어 

• 데이터 클렌징 Data Cleansing : 어떠한 문자열 등에서 내가 원하는 대로 필터링을 하고 사용하는 것
• 전처리 작업 Preprocessing : 데이터 클렌징은 입력값에 대한 편리하게 보기 위해 정리 

import re
import collections

sample = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"] 

def mostCommonWord(self, sample: str, banned: List[str]) -> str:
	words = [word for word in re.sub(r'[^\w]', ' ', sample)
    	.lower().split() 
        	if word not in banned]
    counts = collections.Counter(words)
    
    return counts.most_common(1)[0][0]

print(mostCommonWord(self, sample, banned))

 

---

그룹 애너그램

애너그램 :  일종의 언어유희로 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말한다. 
Ex) 문전박대 --> 대박전문 

애너그램을 판단하는 가장 간단한 방법은 정렬하여 비교하는 것이다.

import collections
def groupAnagrams(strs) -> List[List[str]]:
	anagrams = collections.defaultdict(list)
    
    for word in strs:
    	anagrams[''.join(sorted(word))].append(word)
    
    return list(anagrams.values())

anagrams[''.join(sorted(word))].append(word)

이 부분은 각 단어를 먼저 Sorted를 해준다. 그렇게 하면 eat의 경우 알파벳 순으로 aet로 바뀐 상태가 된다. 

이상 태로 anagrams['aet']의 좌표가 생성되면서, 이 해당 값에 word라는 원래 Eat이 들어가게 된다. 

이런식으로 sorted된 값이 같은 경우에는 같은 좌표의 값으로 매겨지게 된다. 

 

{

  'aet': ['eat', 'tea', 'ate'], 

  'ant': ['tan', 'nat'], 

  'abt': ['bat']

}

 

join을 통해서 다시 문자열로 합칠 수 있다.

b = 'zbdaf'
b = "".join(sorted(b))
print(b)
# 'abdfz'

 sorted() 의 key 옵션 

c = ['ccc', 'aaaa', 'd', 'bb']
sorted(c, key= len)

print(c) 
# ['d', 'bb', 'ccc', 'aaaa']

len 말고도 다양하게 구현이 가능하다.

a = ['cde', 'cfc', 'abc']
sorted(a, key = lambda s: (s[0], s[-1]))
print(a)
# ['abc', 'cfc', 'cde']

---

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