Algorithm

[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..

[LeetCode/릿코드] 215. Kth Largest Element in an Array (220622 daily challenge)

[ 처음 풀이 ] 1. input부터 vector로 주어졌기에, algorithm STL의 sort() 함수를 이용해 vector를 정렬 2. k번째로 큰 원소를 구하면 되므로, 오름차순으로 정렬된 vector에서 (원소의 개수-k)번 index를 return. class Solution { public: int findKthLargest(vector& nums, int k) { sort(nums.begin(), nums.end()); return nums[nums.size()-k]; } };

[LeetCode/릿코드] 383. Ransom Note

[ 처음 풀이 ] String으로 받아온 두 문자열을 그대로 vector로 parsing해서 RansomNote vector에 있는 문자를 처음부터 하나하나 magazine vector에 존재하는 지 따져보고, 있다면 magazine 문자열에서 삭제. 없다면 조건 성립 실패이므로 false 반환. class Solution { public: bool canConstruct(string ransomNote, string magazine) { vector ransom(ransomNote.begin(), ransomNote.end()); vector mag(magazine.begin(), magazine.end()); for (int i = 0; i < ransom.size(); i++) { char toFi..

[LeetCode/릿코드] 234. Palindrome Linked List

[ 처음 풀이 ] 재귀함수를 이용해, input에서 주어지는 Linked List를 반대로 연결한 것을 구하고, ( 1->2->3->2->1의 Reverse라면 1val; ListNode* tempHead = head; getReverse_(tempHead); } void getReverse_(ListNode* node){ if(node->next != nullptr){ ListNode* newNode = new ListNode(node->val); node = node->next; getReverse_(node); startTail->next = newNode; startTail = newNode; } } public: bool isPalindrome(ListNode* head) { getReverse..