문자열 조작
Question 1: 유효한 팰린드롬
입력: ‘Taco cat’
출력: true
풀이 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
기억해야 할 함수
- isalnum(): 영문자, 숫자이면 True를 리턴하는 함수
- pop(): 삭제할 인덱스를 입력하면 삭제될 값을 리턴하고 삭제가 진행된다.
- lower(): 문자열을 모두 소문자로 변경한다.
중요 내용
- pop()은 리스트의 요소들을 다 검사해야 하기 때문에 코드 실행 시간은 O(n) 이다.
풀이 2: 데크 자료형을 이용한 최적화
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
기억해야 할 함수
- collections.deque(): 자료형을 데크로 선언한다.
- popleft(): 가장 왼쪽에 위치한 요소를 삭제하고 삭제한 값을 리턴한다.
중요 내용
- popleft()는 리스트의 제일 왼쪽에 위치한 요소만 검사하므로 코드 실행 시간은 O(1) 이다.
풀이 3: 슬라이싱 사용
def isPalindrome(self, s:str) -> bool:
s = s.lower()
# 정규식으로 불필요한 문자 필터링
s = re.sub('[^a-z0-9]','',s)
return s == s[::-1]
기억해야 할 함수
- re.sub(치환할 문자, 치환하는 값, 문자열): 정규식으로 불필요한 문자를 필터링한다. ^는 not을 의미하므로 [^a-z0-9]는 영문자, 숫자를 제외한 문자를 공백으로 치환하라는 의미이다.
중요 내용
- 슬라이싱은 매우 빠르게 진행되므로 문자열을 조작할 때는 항상 슬라이싱을 우선으로 사용하자!
- s[:]는 문자열의 사본을 입력한다.
- s[::-1]는 문자열을 뒤집는다.
- s[::2]는 문자열을 2칸씩 앞으로 이동하며 슬라이싱한다.
Question 2: 문자열 뒤집기
입력: [‘h’, ‘e’, ‘l’, ‘l’, ‘o’]
출력: [‘o’, ‘l’, ‘l’, ‘e’, ‘h’]
풀이 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()
기억해야 할 함수
- reverse(): 리스트에만 사용 가능. 리스트의 요소를 뒤집는다.
기억해야 할 내용
- 문자열을 뒤집을 떄는 간단하게 슬라이싱을 이용한다 -> s[::-1]
Question 3: 로그 파일 재정렬
- 로그의 가장 앞 부분은 식별자이다.
- 문자로 구성된 로그가 숫자로 구성된 로그보다 앞에 온다.
- 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일한 경우 식별자 순으로 한다.
- 숫자 로그는 입력 순서대로 한다.
풀이 1: 람다와 + 연산자를 이용
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
기억해야 할 함수
- list.sort(key=function): function에 지정한 순서대로 리스트를 정렬한다.
- list.isdigit(): 숫자여부를 판별하는 함수이다.
기억해야 할 내용
- [1,2,3] + [4,5,6] 의 연산을 수행하면 두 리스트가 append된 [1,2,3,4,5,6] 이 나온다.
- 람다 표현식은 다음과 같은 형태이다.
- lambda x:x+2: x값을 받고 x+2를 리턴한다.
Question 4: 가장 흔한 단어
입력: paragraph = ‘bob hit a BALL, and the ball flew after it was hit’ banned = [‘hit’]
출력: ‘ball’
풀이 1: 리스트 컴프리헨션, counter 객체 사용
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]
기억해야 할 함수
- list.sort(key=function): function에 지정한 순서대로 리스트를 정렬한다.
- list.isdigit(): 숫자여부를 판별하는 함수이다.
기억해야 할 내용
- [1,2,3] + [4,5,6] 의 연산을 수행하면 두 리스트가 append된 [1,2,3,4,5,6] 이 나온다.
- 람다 표현식은 다음과 같은 형태이다.
- lambda x:x+2 는 x값을 받고 x+2를 리턴하는 람다식이다.
Question 5: 그룹 에너그램 (재풀이)
문자열 배열을 받아 애너그램 단위로 그루핑하라.
입력: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
출력: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
내 풀이
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
strs_dict = collections.defaultdict(list)
for word in strs:
strs_dict[''.join(sorted(word))].append(word)
return strs_dict.values()
기억해야 할 내용
- sorted()는 string, list 모두 사용이 가능한 반면 sort()는 list만 사용가능하다.
- sorted()는 또한 key 값을 지정하여 지정한 key 값대로 정렬을 하는 것이 가능하다.
Question 6: 가장 긴 팰린드롬 부분 문자열 (재풀이)
가장 기 팰린드롬 부분 문자열을 출력하라.
입력: s = “babad”
출력: “bad”
풀이 1: 중앙을 중심으로 확장하는 풀이
class Solution:
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]
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
기억해야 할 내용
- s[::-1]은 문자열 s를 뒤집는다.
- max()는 key 값을 지정함으로써 key 값을 기준으로 제일 큰 값을 출력한다.
Comments