highlightmoon 님의 블로그

링크 - https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/?envType=company&envId=facebook&favoriteSlug=facebook-three-months난이도 - MediumIntuition1) BFS이 문제는 BFS를 통해 풀 수 있다. 우리는 이 Tree가 Perfect binary Tree임을 알고 있으므로, 매번 1, 2, 4, 8,..개의 노드들을 처리해야한다는 것을 알 고 있다. 따라서 이 값을 추적하면서 BFS를 하면 쉽게 문제를 풀 수 있다."""# Definition for a Node.class Node: def __init__(self, val: int..

링크 - https://leetcode.com/problems/diagonal-traverse/description/?envType=company&envId=facebook&favoriteSlug=facebook-three-months난이도 - MediumIntuition이 문제는 동작 방식을 이해하면 쉽게 풀 수 있다. 먼저 direction을 1 또는 0으로 설정하게 한다(초기값은 1). 그리고 row와 col이 edge를 만날 경우에는 우리는 그것에 대한 경우의 수를 적어 놓아야 한다.Codeclass Solution: def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]: ans = [] rows = len(..

링크 - https://leetcode.com/problems/valid-palindrome-iii/description/?envType=company&envId=facebook&favoriteSlug=facebook-three-months난이도 - HardIntuition1) Bottom-Up DP (2D)우리는 2D list DP를 사용해 이 문제를 풀 수 있다. 알고리즘은 다음과 같다.1. 먼저 DP를 nxn 리스트로 만든 뒤, 0으로 초기화 한다.2. i는 n-2부터 0까지, j는 i+1부터 n-1까지 돌린다.3. s[i] == s[j]이면, 우리는 그 사이의 dp값을 그대로 쓰면 되므로 dp[i][j] = dp[i+1][j-1]이 된다.4. s[i] != s[j]이면, 우리는 그 사이의 dp값에..

링크 - https://leetcode.com/problems/find-duplicate-file-in-system/description/난이도 - MediumIntuitionHash table로 쉽게 풀 수 있는 문제이다. 문제를 잘 이해했다면 어렵지 않을 것이다.1. 먼저 각 path를 " "로 split한다. 첫번째 원소를 directory로 놓고 다음 원소들부터 file_path와 content로 나눠 content를 key, directory + "/" + file_path를 value로 append한다.2. 각 hash table 아이템들을 돌면서 value의 크기가 1 이상인 것들만 ans에 append한다.Codeclass Solution: def findDuplicate(self, ..

링크 - https://leetcode.com/problems/validate-ip-address/description/난이도 - MediumIntuition우리는 각 ip를 그에 맞는 함수에 적용시켜 문제를 풀 수 있다.Codeclass Solution: def validIPAddress(self, queryIP: str) -> str: counter = Counter(queryIP) if counter.get(".", 0) == 3: return self.validateIPv4(queryIP) elif counter.get(":", 0) == 7: return self.validateIPv6(queryIP) ..

링크 - https://leetcode.com/problems/sort-array-by-parity/description/난이도 - EasyIntuition이 문제는 쉬우므로 in-place변경을 통해 Space complexity가 O(1)로 할 수 있는 방법으로 문제를 풀어보겠다.1. 먼저 left, right를 0, len(nums) - 1로 초기화한다.2. left3. 먼저 nums[left]가 홀수이고 nums[right]가 짝수이면, 둘을 swap한다.4. 아니면 둘 다 홀수이거나 둘 다 짝수, 혹은 nums[left]가 짝수이고 nums[right]가 홀수이다. 이때 nums[left]가 짝수이면 left += 1하고, nums[right]가 홀수이면 right -= 1한다.Codeclass..

링크 - https://leetcode.com/problems/3sum/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-three-months난이도 - MediumIntuition우리는 TwoSum문제를 푼 방식과 같은 방법으로 문제를 풀 수 있다.1. nums를 sort한다. 그다음 nums를 for문으로 돌리면서 num이 0보다 크면 앞의 수들은 다 더해도 0보다 크게 되므로 break를 건다.2. 만약 i == 0 이거나 nums[i-1] != nums[i]이면 TwoSum을 한다.3. j = i+1부터 시작하여 하나씩 올려간다. 만약 -nums[i] - nums[j]가 target에 있다면 ans에 답으로 집어넣는다. 그리고 nums[..

링크 - https://leetcode.com/problems/course-schedule-ii/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-three-months난이도 - MediumIntuition우리는 이 문제를 DFS로 풀 수 있다. 푸는 방법은 다음과 같다.1. 먼저 각 코스의 prerequisites의 개수를 나타내는 1차원 배열과, 코스들의 prerequisite관계를 나타내는 graph를 만든다.2. 다음으로 답으로 반환할 빈 list와 방문한 course를 넣을 set을 만든다.3. course를 돌면서 prerequisite개수가 0인 것에 대해서 dfs를 진행한다. dfs를 진행할때는 현재 진행하는 course를 ans..

링크 - https://leetcode.com/problems/minimum-operations-to-write-the-letter-y-on-a-grid/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days난이도 - MediumIntuition Codeclass Solution: def minimumOperationsToWriteY(self, grid: List[List[int]]) -> int: n = len(grid) y_area = 2* (n//2) + (n//2 + 1) others_area = n*n - y_area counter_y = defaul..

링크 - https://leetcode.com/problems/daily-temperatures/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days난이도 - MediumIntuition우리는 Stack을 사용하여 이 문제를 풀 수 있다. 먼저 stack에 값이 있는 지 확인 후, stack의 peak의 온도가 현재 온도보다 낮으면 계속 pop을 해서 pop한 index의 값에 현재 index와의 diff를 집어넣는다. 혹은 우리가 space complexity를 O(1)로 하고 싶다면 오른쪽에서 왼쪽으로 이동하면서 문제를 풀어도 된다.1. 오른쪽에서 왼쪽으로 이동하면서 현재 temperature값을 확인한다. 현재 tempe..