파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자. # 문제 설명 561번 Array Partition I은 n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하는 문제이다. 이 문제는 내가 지금까지 풀었던 문제들 중 가장 효율적으로 작성한 풀이이지 않나 싶다. 규칙을 찾아서 풀어서 효율적으로 나온거 같기도 하다..😀 책 풀이 확인해보니까 내가 푼 방법과 유사하여 따로 설명은 생략하겠다. # 풀이방법 1 - 단순 list와 for문으로 판별 (내 풀이 - 효율적) class Solution: def arrayPairSum(self, nums: List[int]) -> int: nums.sort() result = 0 for _min in n..
파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자. # 문제 설명 121번 Product of Array Except Self은 주어진 주식 가격 배열에서 한 번의 거래로 낼 수 있는 최대 이익을 계산해내는 문제이다. 만약 이익이 없다면, 0을 return 하면 된다. # 풀이방법 1 - 뒤에서부터 고점 계산 후 이익 계산 (내 풀이 - 비효율적) class Solution: def maxProfit(self, prices: List[int]) -> int: maxPrice = -1 maxProfit = 0 # 오른쪽 부터 접근하여, 가장 가격이 비싼 값(고점)과 이익이 가장 큰 값을 계산함 for i in range(len(prices)-1, 0, -1) : if pr..
파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자. # 문제 설명 238번 Product of Array Except Self는 주어진 배열에서 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하는 문제이다. 단 나눗셈 없이 O(n)에 풀이해야 함. # 풀이방법 1 - 왼쪽과 오른쪽 곱셈 후 계산 (내 풀이 - 비효율적) class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: cmltv_f = 1 cmltv_b = 1 front = deque() back = deque() len_nums = len(nums) # 1. 왼쪽/오른쪽 누적 곱 계산후 deque에 저장 ..
파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자. # 문제 설명 5번 Longest Palindrome Substring은 가장 긴 팰린드롬 부분 문자열을 출력하는 문제이다. * 펠린드롬 : 앞뒤가 똑같은 단어나 문장 # 풀이방법 1 - 단순 이중 for문으로 class Solution: def longestPalindrome(self, s: str) -> str: palindroms = "" # 문자열의 첫글자와 끝 글자가 같은 문자열 구함 for startIdx, c in enumerate(s): sameCharIdxGroup = [i for i, ele in enumerate(s) if ele == c and i> startIdx] for endIdx in sam..
파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자. # 문제 설명 49번 Group Anagrams은 문자열 배열을 받아 애너그램 단위로 그룹핑하는 문제이다. * 애너그램 : 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것 # 풀이방법 1 - 정렬 후 딕셔너리에 저장 class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: output = [] anagrams = {} # dictionay for check anagram's Index in 'output' list insertIdx = 0 for _str in strs : sortedStr = "".join(sorted(_str)) if..
파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자. # 문제 설명 937번 Reorder Log Files은 다음 규칙에 따라 로그를 재정렬하는 문제이다. 1. 로그의 가장 앞 부분은 식별자 2. 문자로그는 숫자 로그보다 앞에 온다 3. 문자로그를 정렬할 때 문자가 동일할 경우 식별자 순으로 함 4. 숫자 로그은 입력 순서대로 함 # 풀이방법 1 - lamda와 + 연산자 이용 (책 풀이 참고) class Solution: def reorderLogFiles(self, logs: List[str]) -> List[str]: letterLogs = [] digitLogs = [] for log in logs : if log.split()[1].isalpha() == Tru..
