thumbnail
Python Coding Interview - 2부 6장 | 문자열 조작
Coding Test / Python
2023.01.17.

문자열 조작과 처리 문제엔 어떤 기법들이 쓰이는지에 집중하면서 책을 읽었고 그 내용을 정리해보았다.

01. 유효한 팰린드름

풀이 1. 리스트로 변환

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

문자열의 길이가 1보다 클때까지, pop과 pop(0) 함수를 활용하여 팰린드롬 여부를 판별한다.

풀이 2. 데크 자료형을 이용한 최적화

리스트만으로 충분히 해결 가능하지만, 데크를 사용하면 좀 더 속도를 높일 수 있다.

strs: Deque = collections.deque()

pop(0) 은 O(n) 인 데 비해, 데크의 popleft는 O(1)이기 때문이다.

풀이 3. 슬라이싱 사용

s = s.lower()
# 정규식으로 불필요한 문자 필터링
s = re.sub('[^a-z0-9]', '', s)

return s == s[::-1] # 슬라이싱

파이썬의 슬라이싱을 사용한 풀이이다. 문자열 전체를 한번에 영숫자만 걸러내도록 정규식 으로 처리하였다. 그리고, [::-1] 를 사용하면 문자열을 뒤집을 수 있다.

실행시간 비교

  1. 리스트로 변환 : 304 ms
  2. 데크 자료형을 이용한 최적화 : 64ms
  3. 슬라이싱 사용 : 36ms

문자열 슬라이싱

위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 찾아내는데, 이 과정은 매우 빠르게 진행되므로 문자열을 조작할 때는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리하다. 안녕하세요 를 슬라이싱해본 예제들이다.

S = '안녕하세요'
S[1:-2] == 녕하
# 인덱스 1에서 -2 이전까지

S[:] == 안녕하세요
# 둘 다 생략하면 사본을 리턴한다. 즉, 값을 복사하는 것이다.

S[::2] == 안하요
# 2칸씩 앞으로 이동한다

S[::1] == 안녕하세요
# 1은 기본값으로 동일하다

S[::-1] == 요세하녕안
# 뒤집는다

02. 문자열 뒤집기

풀이 1. 투 포인터를 이용한 스왑

점점 범위를 좁혀가며 내부에서 스왑을 해주면 된다. left, right 를 각각 0, len(s) - 1 로 설정을 해준 다음 순회를 하면서 스왑을 해준다.

풀이 2. 파이썬다운 방식

입력값이 리스트로 제공되므로 다음과 같이 reverse() 함수 를 사용하면 뒤집을 수 있다. 슬라이싱 또한 리스트에서 활용할 수 있으므로 s = s[::-1] 를 해주면된다. 하지만, 이 풀이는 리트코드에서 오류가 나므로, 다음과 같은 트릭을 써주면 된다.

s[:] = s[::-1]

실행시간 비교

  1. 투 포인터를 이용한 순환 : 216ms
  2. 파이썬다운 방식 : 208ms

03. 로그 파일 재정렬

특정 요구 사항들을 얼마나 잘 처리할 수 있는지를 묻는 문제이다. 우선, 문자로 구성된 로그가 숫자 로그보다 이전에 오며, 숫자 로그는 입력 순서대로 둔다. 그렇다면 문자와 숫자를 구분하고, 숫자는 나중에 그대로 이어붙인다. 숫자로그가 문자열로 지정되어 있으므로, 이럴때 사용할 수 있는 함수가 isdigit() 이다.

문자가 동일할 경우 식별자 순으로 정렬 -> 2가지 요소를 기준으로 정렬을 할 때는 람다 표현식 을 사용한다. 문자가 동일한 경우에만 그 앞 요소순으로 정렬되는 형태일 때는 리스트의 각 요소를 풀어서 별도 처리를 해줘야하는데, 람다 표현식이 이럴 때 도움이 된다.

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

04. 가장 흔한 단어

풀이 1. 리스트 컴프리헨션, Counter 객체 사용

마침표, 쉼표 등 단어문자가 아닌 모든 문자를 공백으로 치환하는 전처리 과정이 필요하다.

words = [word for word in re.sub(r'[^\w]', ' ', paragraph)
	.lower().split()
		if word not in banned]

정규식에서 \w는 단어 문자를 뜻하며 ^ 은 not 을 의미한다. 그리고, 리스트 각 요소들의 횟수를 구하고 싶으면 collections.Counter 를 이용해주면 된다.

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

05. 그룹 애너그램

풀이 1. 정렬하여 딕셔너리에 추가

애너그램 -> 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말한다.

각 문자열들을 정렬하여 키 값으로 지정한다음, 원래 문자열 값을 value 로 넣어주는 방식을 택하였다. 문자열도 리스트 처럼 sorted() 함수를 활용할 수 있다. 반환값은 list 여서 ''.join() 함수를 통해 문자열 형태로 합칠 수 있다.

그리고, 존재하지 않는 키를 삽입하려 할 경우, keyError가 발생하므로, 에러가 나지 않도록 매번 키 존재 여부를 체크 안하는 defaultDict() 로 선언한다.

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

풀이 1. 중앙을 중심으로 확장하는 풀이

아직은 이 풀이가 완전히 이해가 되지 않아 다시 한번 이 문제를 꼼꼼히 풀어봐야겠다.

최장 공통 부분 문자열을 찾는 문제이다. 다이나믹 프로그래밍으로도 풀 수 있지만, 좀 더 직관적이면서 훨신 더 성능이 좋은, 투 포인터가 중앙을 중심으로 확장하는 형태로 풀이하였다. 코드 실행 전에 예외처리를 해주면 전체적인 풀이 속도 향상에 매우 큰 도움이 된다.

if len(s) < 2 or s == s[::-1] :
	return s

홀수, 짝수 2개의 투 포인터가 팰린드롬 여부를 판별하면서 슬라이딩 윈도우 처럼 계속 우측으로 이동한다.

def longestPalindrome(self, s) :
	# 팰린드롬 판별 및 투 포인터 확장
	def expand(left, right) :
		while left >= 0 and right < len(s) and s[left] == s[right] :
			left -= 1
			right += 1
		return s[left + 1 : right]

	# 해당 사항이 없을 때 빠르게 리턴
	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