Algorithm/LeetCode

[LeetCode/릿코드] 948. Bag of Tokens - Python

[Medium] https://leetcode.com/problems/bag-of-tokens/ 풀이 tokens 배열을 오름차순 정렬해준 후, Two Pointer 기법을 이용해 풀어주면 쉽게 풀이할 수 있다. curl, curr 이라는 두 개의 커서를 각각 0, len(tokens) 로 초기화한 뒤, 차례로 진행해주면 된다. 현재 power가 왼쪽 커서(curl)의 토큰값보다 크다면 power를 낮추고 score를 올린 뒤(Face-up), 커서를 오른쪽으로 한 칸 이동. 현재 power가 왼쪽 커서(curl)의 토큰값보다 작다면, score가 1 이상이며, 왼쪽 커서와 오른쪽 커서가 같은 곳을 가리키지 않을 때, score를 낮추고 power를 올린다. (Face-down) 왼쪽 커서와 오른쪽 커서..

[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이라면 직전 아이 개..