코딩하는 eroke

문제

예제

Input: prices = [7,1,5,3,6,4]
Output: 5

Constraints:
1 <= prices.length <= 105
0 <= prices[i] <= 104

주식이 1인 시점에서 6인 시점에 팔아야 최대 이득을 볼 수 있고 이득은 5이다.

브루트포스로 풀면 O(n^2)으로 제출 시 타임아웃 에러가 난다.

주식의 최소값과 이득을 계속해서 갱신하는 방법으로 O(n)에 해결해야 하는 문제이다.

풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        minp = sys.maxsize
        
        for p in prices:
            minp = min(p, minp) #최소값 갱신
            result = max(result, p-minp) #이득 갱신
        
        return result

결과

문제 

문자열에서 가장 긴 팰린드롬 문자열을 추출하는 문제이다. (팰린드롬 : 앞뒤가 똑같은 문자열)

(연관문제 : 유효한 팰린드롬)

예제

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

풀이 (python)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        def expand(l:int, r:int)->str: #left, right 이중 포인터
            while l>=0 and r<len(s) and s[l]==s[r]:
                l-=1
                r+=1
            return s[l+1:r] # 인덱스 l부터 r-1까지 
        
        result = ''
        
        if len(s)<2 or s==s[::-1]:  #예외처리
            return s
        
        for i in range(len(s)-1):
            result = max(result,
                         expand(i, i+1), #팰린드롬 길이가 짝수인 경우
                         expand(i, i+2), #팰린드롬 길이가 홀수인 경우
                         key=len)
                         
        return result

투 포인트를 사용해 팰린드롬 길이가 짝수/홀수 인 경우를 구분했고

인덱스를 확장하며 팰린드롬을 리턴하는 expand(left, right) 함수를 만들어 길이 기준 (key=len)으로

최대길이 문자열을 반환했다.

문제

애너그램 : ate=tea=eat > 같은 문자들로 문자열을 재배열

애너그램끼리 그룹짓는 문제이다.

풀이

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        dic = collections.defaultdict(list)
        
        for arr in strs:
            tmp = ''.join(sorted(arr)) #sorted(arr) -> list 반환, sorted("tea")=['a', 'e', 't']
            dic[tmp].append(arr)

        return dic.values()

 sorted()는 리스트, 문자, 숫자 모두 정렬이 가능하다 list 형으로 반환한다. (용도에 맞게 join 하기)

문제

문자열에서 금지된 단어 (banned)를 제외한 단어들 중 가장 빈도수가 높은것을 출력하는 문제이다.

입출력

#Case 1
Input: s = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"

#Case 2
Input: s = "a.", banned = []
Output: "a"

#Case 3
Input: s = "Bob", banned = []
Output: "bob"

풀이

class Solution:
    def mostCommonWord(self, s: str, banned: List[str]) -> str:
        
        word = []       
        dic = collections.defaultdict(int)
        s = s.lower()
        
        for x in s : 
            if x.isalpha() == True:
                word.append(x)
            
            else:
                w = "".join(word) #list > str
                if w not in banned and w != '': 
                    dic[w]+=1
                word=[]
        
        #for문에서 else문 안 탄 경우 딕셔너리 추가 
        w = "".join(word)  
        if w not in banned and w != '': 
            dic[w]+=1
                    
        res = collections.Counter(dic)
        
        #Couter 객체의 가장 빈도수가 높은 key값(단어) return
        return res.most_common(1)[0][0]

문제

팰린드롬 : 앞뒤가 똑같은 단어/문장
주어진 문자열이 팰린드롬인지 검증하는 문제이다. 대소문자는 구분하지 않고, 영문자와 숫자만 해당된다.

#예제
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

풀이

#1 deque 사용 
class Solution:
    def isPalindrome(self, s: str) -> bool:
        
        s = s.lower()
        dq = collections.deque()
        
        for x in s:
            if x.isalnum():
                dq.append(x)
                
        while len(dq) > 1 : 
            if dq.popleft() != dq.pop():
                return False
            
        return True

#2 슬라이딩 사용 
class Solution:
    def isPalindrome(self, s: str) -> bool:
        
        s = s.lower()
        result = []
        
        for x in s:
            if x.isalnum():
                result.append(x)
                
        if result == result[::-1] :    
            return True
       
        return False

결과