ALL

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자. # 문제 설명 15번 3Sum은 배열을 입력받아 합으로 0을 만들 수 있는 3개의 요소를 출력하는 문제이다. 단 결과에 중복된 요소 집합이 포함되면 안 된다. 위 문제를 풀려고 시도했지만 시간 초과로 떴고, 다른 방법은 생각나지 않아 우선 책 풀이를 참고하였다. # 시도 1 (Time Limit Exceeded) - 3중 for문 ...당연히 시간 초과로 뜸. 더보기 class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: result =[] nums.sort() len_nums = len(nums) print(nums) for i in range(..

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 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..