highlightmoon 님의 블로그

링크 - https://leetcode.com/problems/merge-intervals/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - MediumIntuition이 문제는 Sorting으로 풀 수 있다. 먼저 list를 각 원소의 첫 번째 값을 기준으로 sorting한다. (유용한 파이썬 내장함수가 있는데, sorted(list, key=lambda x:x[0])를 쓰면 된다.) 그 다음, 첫번째 원소부터 시작해서 다음 비교하는 원소들의 두 번째 값을 비교한다. 예를 들어, (1,4)와 (3,5)는 4와 3을 비교해서 4가 3보다 크거나 같으므로 두개의 interval들은 합칠 수 있다. 따라서 4와..

링크 - https://leetcode.com/problems/powx-n/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - MediumIntuition1) Binary Exponentiation (Recursive)2^10인 경우를 보자. 이는 (2^2)^5 = 4^5로 변환 가능하다. 또한 이는 (4^2)^2 * 4로 변환가능하다.즉 n을 2로 계속 나누면서 나온 결과를 곱하면 되는 것이다. n이 짝수이면 x = x*x로 하면 되고, n이 홀수이면 x = x*x로 하되, rem이라는 변수를 따로 줘서 거기에 x를 곱해준다. 그리고 맨 마지막에 rem을 곱해주면 된다.class Solution: def binaryExp(..

링크 - https://leetcode.com/problems/k-closest-points-to-origin/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - MediumIntuition1) Max Heap and Max Priority QueueHeap을 사용하면 모든 포인트들을 돌면서 거리가 가장 짧은 k개만 유지시킬수 있다. 이때 heap에 넣을때는 (-distance, point)형태의 튜플로 넣어야 가장 적은 거리의 포인트들을 유지시킬 수 있다.class Solution: def kClosest(self, points: List[List[int]], k: int) -> List[List[in..

링크 - https://leetcode.com/problems/range-sum-of-bst/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - EasyIntuitionDFS로 탐색하며 값을 비교하면서 풀 수 있는 문제이다.또한 BST이기 때문에 현재 node의 val이 low보다 크면 왼쪽 child를 탐색하고, node의 val이 high보다 작으면 오른쪽 child를 탐색하면 시간을 줄일 수 있다.Code# Recursive# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=..

링크 - https://leetcode.com/problems/valid-word-abbreviation/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - EasyIntuition두 개의 포인터를 사용해서 문제를 풀면 된다. 각각 word와 abbr을 가리키면 되고, abbr에서 isnumeric()이 True가 되면 우리는 번호를 뽑아낸 뒤, word를 가리키는 포인터에 더하면된다. 그러면서 틀린 글자가 나오면 False, 아니면 두개의 포인터가 글자 끝까지 가면 True를 반환하면 된다.Codeclass Solution: def validWordAbbreviation(self, word: str, ..

링크 - https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - MediumIntuition1) Using a Stack and String Builder우리는 먼저 괄호에 대한 스택을 유지하면서 글자들을 탐색해야 한다. 1. ans = "", opening_idx = [], idx_to_subs = 0으로 초기화한다.2. 글자가 나오면 ans에 붙인다.3. "("가 나오면 opening_idx에 현재 i값을 넣고 ans에 붙인다.4. ")"가 나오면 opening_idx살펴본다. 만약 ..

링크 - https://leetcode.com/problems/binary-tree-vertical-order-traversal/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - MediumIntuition1) Breadth-First Search (BFS)이 문제에서는 모든 노드들이 level by level로 접근되어 저장되어야 하므로 BFS가 가장 적합한 알고리즘이라고 생각이 들 것이다. 그리고 horizontal order는 hash table로 저장하여 나중에 순서대로 접근하면 모든 노드들이 left-to-right, up-to-bottom형태로 저장이 될 것이다.# Definition for a ..

링크 - https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - MediumIntuition1) Find q in p's children, and find common ancestor이 방법은 먼저 q가 p의 children node들 중에 있다는 가정부터 시작한다. 여기서는 dfs를 통해 이 값을 찾아낸다. 만약 존재한다면 p를 반환하면 된다.q가 p의 children node들 중에 없다면, 다음 방법으로는 p와 q의 조상들을 비교해야한다. 따라서 먼저 p의 조상들을 set()에..

링크 - https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - MediumIntuition이 문제는 여러 방법으로 풀 수 있다. 일단 우리는 p와 q노드를 찾은 뒤, 위로 다시 올라가는 backtracking을 사용하여 lca를 찾아야 한다.1) Recursive Approach이 방식은 트리를 DFS방식으로 p와 q노드를 먼저 찾는 방식이다. 그리고는 찾은 결과를 boolean flag를 사용하여 lca를 찾아내는 방법이다.1. 루트 노드부터 시작해서 DFS 탐색을 시작한다.2. 만약 ..

링크 - https://leetcode.com/problems/kth-largest-element-in-an-array/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - MediumIntuition이 문제는 다양한 방법으로 풀 수 있다.1) Sort단순히 주어진 배열을 sorting하고 k번째 값을 찾는 방식이다. 직관적이지만 인터뷰에서는 더 나은 솔루션을 생각할 필요가 있다.class Solution: def findKthLargest(self, nums, k): nums.sort(reverse=True) return nums[k - 1]Time Complexity: O(nl..