전체 글

[LeetCode] 1696. Jump Game VI

접근1 DP.. Top-Down 방식으로 재귀를 이용해 구현. i번째부터 점프를 시작할 때의 최대 score를 score[i] 라고 저장 (메모이제이션) 그렇게 score[0]을 구해가는 방법. class Solution: def maxResult(self, nums: List[int], k: int) -> int: lenOfnum = len(nums) # index 'i' 부터 시작했을 때의 최대 score score = {lenOfnum-1: nums[lenOfnum-1]} # end index부터 반대로 순회 def dp(i): a = score.get(i, None) if i + 1 == lenOfnum: return nums[lenOfnum-1] if a != None: retur..

[LeetCode] 97. Interleaving String

접근1 - 실패 (DP, List 이용) 일단 Topic을 보니.. DP가 들어있었는데.. DP 너무 어려워 ㅠ s3를 순회하며 s1과 s2 두 쪽 모두에 있는 알파벳을 맞닥뜨렸을 때 처리하는 게 관건일 듯. s1 = "aabbc" s2 = "abbcd" s3 = "aababbbccd" 잘 생각이 안 나서, discuss 쪽을 살짝 들여다봤음. https://leetcode.com/problems/interleaving-string/discuss/32076/Simple-Python-DP-solution 이거. 이런 경우, s3의 첫 index부터 s1에서 빼올지 s2에서 빼올지.. 두 경우 모두를 선택하여 모두 따져봐야 함. s3의 모든 문자를 순회하면서, s1과 s2의 현재 진행 위치를 저장하며 가면 ..

[LeetCode] 509. Fibonacci Number

접근 얘는... 딱히 설명할 필요가 없을듯 기본적인 피보나치 수열 문제! class Solution: def fib(self, n: int) -> int: num1 = 1 num2 = 1 temp = 0 if n == 0: return 0 if n == 1 or n == 2: return 1 for _ in range(n-2): temp = num1 + num2 num1 = num2 num2 = temp return num2

[LeetCode/릿코드] 128. Longest Consecutive Sequence (220705 daily challenge)

접근1 우선 제일 먼저 생각난 접근은, 리스트를 정렬한 후 하나씩 pop하며 제일 긴 연속된 횟수를 산정하는 것. 그러나 시간복잡도가 O(n)으로 제한되어 있으므로, O(nlogn)인 sort() 함수를 써서 정렬할 수 없음. 그래서 다음에 든 생각은 삽입, 삭제에 적은 시간이 드는 최소 힙을 이용하는 것. 그러나 최소 힙의 삽입, 삭제도 O(logn)이므로, 총 O(nlogn)이 되어 O(n)보다 커지게 됨. 그러면.. 더 빠른 남은 건 Hash밖에 없는데.. 해시로 어떻게 접 근 을 할 까... 리스트에서 최솟값, 최댓값 찾기 - O(n) 딕셔너리에 리스트의 값들을 key값으로 지정하여 추가 - O(n) 최솟값부터 최댓값까지 dictionary에 key값이 있는 지 검사하며, 최대로 반복되는 횟수 측..

[LeetCode/릿코드] 1710. Maximum Units on a Truck (220701 daily challenge)

간단해서 설명할 게 없음 class Solution: def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int: sumOfUnits = 0 boxList = sorted(boxTypes, key=lambda x: x[1], reverse=True) for i in boxList: if truckSize >= i[0]: truckSize -= i[0] sumOfUnits += i[0] * i[1] elif truckSize > 0 and truckSize < i[0]: sumOfUnits += i[1] * truckSize truckSize = -1 else: break return sumOfUnits

[LeetCode/릿코드] 376. Wiggle Subsequence (220703 daily challenge)

접근 일단 wiggle sequence 를 판정하는 건 어렵지 않다. index 순서로 순회하며 두 값의 차이가 +, -, +, - 를 반복하는 지 확인하면 됨. + 다음 - 가 오지 않으면 다음 인덱스로 넘어가서 다시 비교 비교 또 비교 그렇게.. 최대 길이를 구하면 될 듯 class Solution: def wiggleMaxLength(self, nums: List[int]) -> int: pre_gap = 0 now_gap = 0 count_length_sub = 1 if len(nums) != 1: for num1, num2 in zip(nums, nums[1:]): now_gap = num2 - num1 wiggle = now_gap * pre_gap if wiggle < 0: # now_gap..

[LeetCode/릿코드] 135. Candy (220704 daily challenge)

접근 rating 리스트 두 번째부터 검사 시작. 현재 index의 rating 다음 index의 rating 이라면 count++ 하며 계속 비교. 그러다 현재 index의 rating 다음 index의 rating 의 현재 index = 3 이라면 index = 4 부터 사탕을 4, 3, 2, 1 순으로 지급. index = 3 에는 index=2가 받은 사탕 + 1 과 count(5) 중 더 큰 것을 지급.) 현재 index의 rating = 다음 index의 rating 의 경우는 직전 index rating < 현재 index rating이라면 직전 아이 개..

[LeetCode/릿코드] 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts (220702 daily challenge)

접근 - 1 가로, 세로의 잘린 간격을 리스트에 담아 저장. 가로, 세로의 간격 리스트를 이중for문으로 순회하며 곱해서 최대의 넓이를 구해냄. class Solution: def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int: horizontalCuts.sort() verticalCuts.sort() horizonGap = [] verticalGap = [] maxCuttedArea = 0 # horizonGap, verticalGap 리스트에 잘린 간격의 칸 수를 순서대로 삽입. horizonGap.append(horizontalCuts[0]) for num1, num2 in zip(hor..