highlightmoon 님의 블로그

링크 - 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..

링크 - https://leetcode.com/problems/possible-bipartition/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days난이도 - MediumIntuition우리는 BFS를 통해 이 문제를 풀 수 있다. 먼저 모든 노드들의 색깔을 -1로 설정한다. 그리고 dislikes를 통해 graph를 만들어주고, bfs를 통해 인접한 노드들이 같은 색깔을 가지는지를 확인한다. 만약 같은 색깔일 경우, 서로 싫어하는 사람들끼리 같은 팀에 있다는 뜻이므로 False를 반환해야 한다.Codeclass Solution: def possibleBipartition(self, n: int, dislikes: L..

링크 - https://leetcode.com/problems/subarray-sums-divisible-by-k/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days난이도 - MediumIntuition우리는 따로 k길이를 갖는 list를 사용하여 이 문제를 풀 수 있다. 우리는 modulo를 사용하여 항상 0 - k-1값을 가지는 개수를 알 수 있으므로 nums를 for문으로 지나가며 생기는 modulo값을 list에 더해가며 문제를 풀 수 있다.Codeclass Solution: def subarraysDivByK(self, nums: List[int], k: int) -> int: n = len(num..

링크 - https://leetcode.com/problems/path-sum-ii/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days난이도 - MediumIntuition우리는 Binary Search Tree를 통해 이 문제를 풀 수 있다. 중요한점은 cur_path로 매 노드마다 현재 path를 list로 넘길 때, 현재 노드의 값을 append해주고 탐색이 끝나면 cur_path에서 pop을 해줘야 다른 노드 탐색에 영향이 없다.Code# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=N..

링크 - https://leetcode.com/problems/number-of-distinct-islands/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days난이도 - MediumIntuition우리는 이문제를 DFS와 pattern을 사용해서 풀 수 있다. 먼저 각 row와 col로 이동할때 pattern을 더해주고, dfs가 끝날때 "0"을 더해줌으로써 unique한 pattern을 가져갈수 있다. list를 set에 더해줄때는 꼭 tuple()을 사용하는것을 잊지 말자.Codeclass Solution: def numDistinctIslands(self, grid: List[List[int]]) -> int: ..

링크 - https://leetcode.com/problems/super-egg-drop/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days난이도 - HardIntuition우리는 dp를 통해서 이 문제를 풀 수 있다. dp[move][egg]를 egg의 달걀이 주어지고 move만큼 움직일 수 있다고 할 때, 우리가 체크할 수 있는 가장 maximum floor값을 가진다고 생각하자.그렇다면 공식은 다음과 같다dp[move][egg] = dp[move-1][egg-1] + dp[move-1][egg] + 1이 공식은 다음과 같은 뜻을 가진다- 만약 move를 한번 한다고 할 때,- 만약 달걀이 깨진다면, 우리는 dp[move..

링크 - https://leetcode.com/problems/rotate-array/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days난이도 - MediumIntuition1) Cyclic Replacements우리는 계속해서 값을 바꿔주는 식으로 이 문제를 풀 수 있다.class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) k %= n start..