[TIL] 파이썬 알고리즘 인터뷰 Day_1 # 1 문자열 조작

 

 파이썬 알고리즘 인터뷰라는 책을 새로 구매하였다.

내년 상,하반기 코딩테스트 준비를 위해서 구매하였고 가격은 무려 38,000원이다. 

앞서 간략하게 자료구조에 관한 글을 쓴 적이 있지만 아직 제대로 알고있지 못하므로 이 책을 통해 알아가야겠다.

 

👜[TIL] Day 1 문자열 조작 -1

파이썬 알고리즘 인터뷰라는 책을 새로 구매하였다.

내년 상,하반기 코딩테스트 준비를 위해서 구매하였고 가격은 무려 38,000원이다.

앞서 간략하게 자료구조에 관한 글을 쓴 적이 있지만 아직 제대로 알고있지 못하므로 이 책을 통해 알아가야겠다.

모든 자료는 파이썬 알고리즘 인터뷰를 참조하였으며, 개인적인 공부를 위해서 작성하였다.

1. Valid Palindrome (유효한 팰린드롬)

• 입력 : “A man, a plan, a canal: Panama”
• 출력 : true
• 입력 : “race a car”
• 출력 : false

Solution 1

#First Method
def isPalindrome(self, s: str) -> bool:  
    texts = []  # Create Texts
    for chars in s:  
        if chars.isalnum():  # Check str
            texts.append(chars.lower()) # Convert to Lower alphabet 
            
  # Check Palindrome
    while len(texts) > 1:  
        if texts.pop(0) != texts.pop():  
            return False  
  
 return True

우선 첫번째 Solution은 리스트로 변환한 후 팰린드롬을 판단한다.
여기서 쓰인 pop은 스택에서 쓰이는 것으로 pop(0)은 맨 앞의 값을 가져오고 pop()은 맨 뒤의 값을 가져온다.

Solution 2

# Second Method  
import collections  
from typing import Deque

  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

두번째 방법은 데크 자료형을 이용한 방법이다. Python의 collections 모듈을 이용하는데 Solution1에 비해서 실행 시간이 줄어들었다.

Solution 3

# Third Method  
import re
	def isPalindrome(self, s: str) -> bool:  
	    s = s.lower()  
	    # Using Regex
		s = re.sub('[^a-z0-9]','',s)  
  
	    return s == s[::-1]

세번째 방법은 정규표현식을 이용한 방법이다. [^a-z0-9]는 특수문자를 제외한 문자열만을 추출하는 정규식이며 ''을 통해 기타 구문을 없애준다.

2. Reverse String

• 입력 1 : s = [“H”, “e”, “l”, “l”, “o”]
• 출력 1 : [“o”, “l”, “l”, “o”, “h”]
• 입력 2 : s = [“H”, “a”, “n”, “n”, “a”, “h”]
• 출력 2 : [“h”, “a”, “n”, “n”, “a”, “H”]

def reverseString(self, s : list[str]) -> None:  
  
    s.reverse()

reverse()쓰면 끝이다.

3. Reorder Log Files

• 로그를 재정렬하라. 기준은 다음과 같다.
  1. 로그의 가장 앞 부분은 식별자다.
  2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다.
  3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다.

숫자 로그는 입력 순서대로 한다.

 

• 입력 : 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”]

class Solution:  
    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)  
        # 2개의 키를 Lambda을 이용해 정렬  
  letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))  
        return letters + digits  
  
  
a = Solution()  
logs = ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]  
print(a.reorderLogFiles(logs))

이 부분에서 중요한 곳은 lambda의 활용이다.
lambda는 식별자 없이 실행 가능한 함수다.

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

여기서 lambda를 이용해서 split()[1:]의 원소 즉 맨앞의 원소를 제외한 문자를 기준으로 정렬하고, 문자가 동일한 경우에만 번호순으로 정렬하는 형태를 lambda표현식을 통해 함수의 생성 없이 정렬이 가능하다.

4. Most Common Word

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

 

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

import re  
from collections import Counter  
  
# paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."  
paragraph = "a, a, a, a, b,b,b,c, c"  
banned = ["a"]  
filtered_paragraph = re.sub(r'[^\w]',' ',paragraph)  
params = filtered_paragraph.lower()  
texts = params.split()  
filtered_text = []  
for text in texts:  
    if text not in banned:  
        filtered_text.append(text)  
  
counts = Counter(filtered_text)  
print(counts.most_common(1)[0][0])

class에 넣지않고 그대로 풀었다. 정규표현식을 안쓰려고 노력해보았으나… Failed 그냥 쓰련다.

5. Group Anagrams

Input: strs = [“eat”,“tea”,“tan”,“ate”,“nat”,“bat”]
Output: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
Input: strs = [""]
Output: [[""]]
Input: strs = [“a”]
Output: [[“a”]]

import collections

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagram = collections.defaultdict(list)

        for words in strs:
            anagram[''.join(sorted(words))].append(words)
        
        return anagram.values()

이 문제를 풀면서 defaultdict 라는 것을 처음 사용해보았다. 우선 Python의 sorted()을 사용하게되면 리스트 형태의 값을 리턴하게된다.
이를 join()을 이용해 합쳐 리스트의 값을 키로 하는 딕셔너리로 생성한다.
defaultdict()는 에러가 나지 않도록 해주는 역할을 한다.
이 문제는 join()과 sorted()의 사용법과 KeyError을 회피하기 위한 defaultdict의 사용법을 알아보았다.

Written with StackEdit.