Algorithm/LeetCode

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

[LeetCode/릿코드] 13. Roman to Integer

[ 처음 풀이 ] 입력받은 로마 숫자를 하나하나 변환하여 숫자의 배열로 만들고, ( XIV -> 10, 1, 5 ) 숫자의 배열을 index=0 부터 끝까지 조사하여, 앞의 숫자가 뒤의 숫자보다 작은 경우 ( num[i] < num[i+1] ) 에만 그 두 숫자의 차를 구해 다시 집어넣은 후, 마지막에 총 합계를 구했다. 문제에도 쓰여 있듯, IV, IX, XL, XC, CD, CM을 처리해주는 방법만 고민해 본다면 어렵지 않은 문제였던 것 같음. class Solution { public: int romanToInt(string s) { vector num; int sum = 0; for (int i = 0; i < s.length(); i++) { switch (s[i]) { case 'I': num..