Goooooood

* leetcode 121. Best Time to Buy and Sell Stock Q. 한 번의 거래로 낼 수 있는 최대 이익을 산출하라. # 입력 [7, 1, 5, 3, 6, 4] # 출력 5 # 1일 때 사서 6일 때 팔면 최대 5의 이익을 얻는다. 풀이 1. 브루트 포스로 계산 # O(n^2)로 사고 팔고를 반복하여 최대 이익을 구한다. def maxProfit(prices: List[int]) -> int: max_price = 0 for i, price in enumerate(prices): for j in range(i, len(prices)): max_price = max(prices[j] - price, max_price) return max_price 이 풀이법은 시간 복잡도가 O(n..

* leetcode 238. Product of Array Except Self Q. 배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라. # 입력 [1, 2, 3, 4] # 출력 [24, 12, 8, 6] # 나눗셈을 하지 않고 O(n)으로 풀이하라. 풀이 1. 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈 # 자신을 제외한 왼쪽 곱셈 결과 # [1, 1, 2, 6] # 자신을 제외한 오른쪽 곱셈 결과 # [24, 12, 4, 1] # 이 둘을 곱하면 # [ 1, 1, 2, 6] # [24, 12, 4, 1] # [24, 12, 8, 6] -> 답 def productExceptSelf(nums: List[int]) -> List[int]: out = [] ..

* leetcode 561. Array Partition 1 Q. n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라. # 입력 [1, 4, 3, 2] # 출력 [4] # 설명 n은 2가 되면, 최대 값은 4이다. min(1, 2) + min(3, 4) = 4 풀이 1. 오름차순 풀이 최대 min()을 만들기 위해서 내림차순으로 배열을 만들면 항상 최대 min() 페어를 만들 수 있다는 점을 활용한다. 이때, 문제에서 배열 입력값은 2n개일 것이기 때문에 오름차순으로도 같은 결과가 나온다. def arrayPairSum(nums: List[int]) -> int: sum = 0 pair = [] nums.sort() for n in nums: pair.append(n) ..

* leetcode 15. 3Sum Q. 배열을 입력받아 합으로 0을 만들 수 있는 3개의 앨리먼트를 출력하라 # 입력 nums = [-1, 0, 1, 2, -1, -4] # 출력 [ [-1, 0, 1], [-1, -1, 2] ] 풀이 1. 브루트 포스로 계산 # 3개의 포인터를 이용하여 모두 더해서 0이 되는 값들을 찾는다. def threeSum(nums: List[int]) -> List[List[int]]: results = [] nums.sort() # n^3 반복 for i in range(len(nums) - 2): # 중복값 제거 if i > 0 and nums[i] == nums[i - 1]: continue for j in range(i + 1, len(nums) - 1): if j >..

* leetcode 42. Trapping Rain Water Q. 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. # 입력 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] # 출력 6 높이와 너비 모든 공간을 차례대로 모두 살펴보면 O(n^2)에 풀이가 가능하지만 효율적이지 않기 때문에 투 포인터나 스택을 사용하여 O(n)으로 풀이해야 한다. 풀이 1. 투 포인터를 최대로 이동 def trap(height: List[int]) -> int: if not height: return 0 volume = 0 left, right = 0, len(height) - 1 left_max, right_max = height[left], height[right] while l..

* leetcode 1. Two Sum Q. 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라. # 입력 nums = [2, 7, 11, 15], target = 9 # 출력 [0, 1] 풀이 1. Brute-Force 계산 # 모든 경우의 수 계산 def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: return [i, j] 풀이 2. in을 이용한 탐색 # 첫번째 풀이와 동일한 시간 복잡도 O(n^2)이지만 상수항이 이전에 비해 작아서 더욱 빠르다. def twoSum(s..

* leetcode 5. Longest Palindrome Substring Q. 가장 긴 팰린드롬 부분 문자열을 출력하라. # 입력 "babad" # 출력 "bab" or "aba" 풀이 1. 중앙을 중심으로 확장하는 풀이 def logestPalindrome(s: str) -> str: def expand(left: int, right: int) -> str: # 팰린드롬 여부를 체크하며 포인터 확장 while left >= 0 and right

* leetcode 49. Group Anagrams Q. 문자열 배열을 받아 애너그램 단위로 그룹핑하라. # 입력 ["eat", "tea", "tan", "ate", "nat", "bat"] # 출력 [ ["ate", "eat", "tea"], ["nat", "tan"], ["bat"] ] 풀이 1. 정렬하여 딕셔너리에 추가 def groupAnagrams(self, strs: List[str]) -> List[List[str]]: # defaultdict를 사용하면 항상 디폴트 키를 생성해주기 때문에 KetError를 피할 수 있다. anagrams = collections.defaultdict(list) for word in strs: # sorted로 정렬한 문자열을 키값으로 사용하기 위해 joi..

* leetcode 819. Most Common Word Q. 금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉽표 등) 또한 무시한다. # 입력 paragraph = 'Bob hit a ball, the hit BALL flew far after it was hit.' banned = ["hit"] # 출력 "ball" 풀이 1. 리스트 컴프리헨션, Counter 객체 사용 def mostCommonWord(self, paragraph: str, banned: List[str]) -> str: # 정규식을 사용한 전처리 # \w는 단어 문자(word character를 뜻하며, ^는 not을 의미하며 따라서 paragraph의 모든 # 단어 ..

* leetcode 937. Reorder Log Files Q. 로그를 재정렬하라. 기준은 다음과 같다. 로그의 가장 앞 부분은 식별자다. 문자로 구성된 로그가 숫자 로그보다 앞에 온다. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다. 숫자 로그는 입력 순서대로 한다. # 입력 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. 람다와 + 연산자를 이용 def reorderLogFiles(self, l..