파이썬 알고리즘 인터뷰 - Day 2 #2

원종운·2020년 7월 17일

유효한 팰린드롬

리트코드 125번 문제 : https://leetcode.com/problems/valid-palindrome/
주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

입력 1 : s = "A man, a plan, a canal: Panama"
출력 1 : true
입력 2 : s = "race a car"
출력 2 : false

풀이 1) 슬라이싱 기법

실행 속도 : 48 ms

class Solution:
    def isPalindrome(self, s: str) -> bool:
    	# 리스트 컴프리헨션을 사용하여 문자열 내의 문자 중 알파벳 또는 숫자만 
        # 소문자로 변환하여 리스트로 생성
        strs = [char.lower() for char in s if char.isalnum()] 
        # if forward equals reverse, it is palindrome
        return strs == strs[::-1] 

solution = Solution()
test_case: str = "A man, a plan, a canal: Panama"
result: bool = solution.isPalindrome(test_case)
print(result) # 결과 : True

풀이 2) 리스트를 이용한 큐, 스택 사용

실행 속도 : 272 ms

class Solution:
    def isPalindrome(self, s: str) -> bool:
    	# 리스트 컴프리헨션을 사용하여 문자열 내의 문자 중 알파벳 또는 숫자만
        # 소문자로 변환하여 리스트로 생성
        strs: List[str] = [char.lower() for char in s if char.isalnum()] 

	# first and last char, thus at least length is 2
        while(len(strs) > 1):
            # if first element not qeuals last element, 
            # it is not palindrome
            if strs.pop() != strs.pop(0): 
                return False 
            
        return True # it is palindrome
        
solution = Solution()
test_case: str = "A man, a plan, a canal: Panama"
result: bool = solution.isPalindrome(test_case)
print(result)

풀이 3) Deque 사용

실행 속도 : 52 ms

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs: Deque = collections.deque() # using deque for performance
		
        # for loop s
        for char in s: 
            # if char is alpabet or number
            if char.isalnum():
                # convert char to lower char, then appends char
                strs.append(char.lower()) 
	
        # first and last char, thus at least length is 2
        while len(strs) > 1:  
            # if first element not qeuals last element, 
            # it is not palindrome
            if strs.pop() != strs.popleft(): 
                return False 
                
        return True # it is palindrome

solution = Solution()
test_case: str = "A man, a plan, a canal: Panama"
result: bool = solution.isPalindrome(test_case)
print(result)

문자열 뒤집기

리트코드 344번 문제 : https://leetcode.com/problems/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"]

풀이 1) 스왑

실행 속도 : 224ms

class Solution:
    def reverseString(self, s: List[str]) -> None:
        for i in range(len(s) // 2): # for loop
            s[i], s[len(s) - 1 - i] = s[len(s) - 1 - i], s[i] # swap

풀이 2) 투포인터 기반 스왑

실행 속도 : 220 ms

class Solution:
    def reverseString(self, s: List[str]) -> None:
        left, right = 0, len(s) - 1 # init left, right 

        while (left < right): 
            s[left], s[right] = s[right], s[left] # swap
            left += 1 # left pointer increase
            right -= 1 # right pointer decrease

풀이 3) 리스트 내장 함수

실행 속도 : 196 ms

class Solution:
    def reverseString(self, s: List[str]) -> None:
        s.reverse() # using reverse function in list object

풀이 4) 슬라이싱

실행 속도 : 212 ms

class Solution:
    def reverseString(self, s: List[str]) -> None:
        s[:] = s[::-1] # if s = s[::-1] is not working, this is trick

로그 파일 재정렬

리트코드 937번 문제 : https://leetcode.com/problems/reorder-data-in-log-files/
로그를 재정렬하라. 기준은 다음과 같다.
1. 로그의 가장 앞 부분은 식별자다.
2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다.
3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다.
4. 숫자 로그는 입력 순서대로 한다.

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

풀이 1) 기본적인 풀이

실행 속도 : 40 ms

class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        letters, digits = [], [] # digit list, letter list
        
        for log in logs: # for loop
            if log.split()[1].isdigit(): # if log is digit
                digits.append(log) # log appends digits(digit list)
            else: # this case is letter log
                letters.append(log) # log appends letters(letter list)
		# first priority is after identifier, 
        # second priority is identifier
        letters.sort(key=lambda id: (id.split()[1:], id.split()[0]))
        return letters + digits # first letter logs, second digit logs

가장 흔한 단어

리트코드 819번 문제 : https://leetcode.com/problems/most-common-word/
금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대 소문자 구분을 하지 않으며, 구두점(마췸표, 쉼표 등) 또한 무시한다.

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

풀이 1) 기본적인 풀이

실행 속도 : 36 ms

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
    	# preprocessing using regular expression and list comprehension
        words: List[str] = [word for word in re.sub(r'[^\w]', ' ', paragraph).lower().split() if word not in banned]
        # counting word using Couter Object
        counter_dict: Counter = collections.Counter(words)
        # return first most common word
        return counter_dict.most_common(1)[0][0]

solution = Solution()
# test_case 1
paragraph: str= "Bob hit a ball, the hit BALL flew far after it was hit."
# test_case 2
banned: List[str] = ["hit"]

result: List[str] = solution.mostCommonWord(paragraph, banned)
print(result) # 출력 : ["ball"]

그룹 애너그램

리트코드 49번 문제 : https://leetcode.com/problems/group-anagrams/
문자열 배열을 받아 애너그램 단위로 그룹핑하라.

입력 : strs = ["eat","tea","tan","ate","nat","bat"]
출력 : [["bat"], ["nat","tan"], ["ate","eat","tea"]]

풀이 1) 애너그램 특성 이용 + 딕셔너리

실행 속도 : 96 ms
애너그램은 정렬할 경우 모두 같은 값을 가지는 특성이 있습니다. 따라서 단어를 모두 정렬한 후 그 단어를 키로 사용하여 그룹핑하는 방식입니다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams: dict = collections.defaultdict(list) # default value is list object

        for word in strs: # for loop
            anagrams[''.join(sorted(word))].append(word) # add value in dict

        return list(anagrams.values()) # return anagrams