one line of code at a time

https://leetcode.com/problems/number-of-provinces/ n개의 도시 (aka. 노드)가 있는데 이 도시들이 직접적으로나 간접적으로 연결이 되면, 하나의 province로 간주한다. 그렇게 했을 때 총 몇 개의 province가 있는지 구하는 문제이다.  isConnected 라는 인접 행렬 (adjacent matrix)이 주어져 있다.  class Solution(object): def findCircleNum(self, isConnected): num_prov = 0 visited = set() def dfs(start): pass return num_prov 처음 뼈대는 이렇게 잡을 수 있..

https://leetcode.com/problems/path-sum-ii/description/  class Solution(object): def pathSum(self, root, targetSum): result = [] if not root: return result def dfs(root, curr_sum, curr_list): curr_sum += root.val temp = curr_list + [root.val] if root.left: dfs(root.left, curr_sum, temp) if root.right: ..

https://leetcode.com/problems/path-sum/description/ 루트노드부터 단말노드까지 노드의 val 값을 더했을 때 targetSum과 같아지는 path가 있으면 true, 없으면 false를 반환하는 문제이다. class Solution(object): def hasPathSum(self, root, targetSum): def dfs(root, curr_sum): if not root: return False curr_sum += root.val if not root.left and not root.right: return c..

https://leetcode.com/problems/count-good-nodes-in-binary-tree/ 이 문제가 2021년 마이크로소프트 코테에서 최다 빈출 문제였었다고 한다.  goodnode라는 건 root로부터 시작해서 특정 위치까지 왔을 때 자기보다 큰 노드가 없다면 그 노드를 good node로 정의할 것이다. preorder 순회를 하는데 이전 노드들의 최대값과 현재 노드값을 비교해서 만약에 현재 노드가 크다면, good node이므로 +1을 해준다. class Solution(object): def goodNodes(self, root): def dfs(root, max_value): if not root: ..

https://leetcode.com/problems/leaf-similar-trees/ 이진트리가 2개 주어지면 그것의 leaf node가 같은지, 다른지를 판단하는 문제이다.DFS로 트리를 탐색해서 left node와 right node가 없는 노드라면 (=leaf node), 리스트에 추가해주면 된다. class Solution(object): def leafSimilar(self, root1, root2): def dfs(root, leaf): if not root: return if not root.left and not root.right: # leaf node has no chil..

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/description/ 이진 트리가 주어졌을 때 각 레벨별로 합을 구하는데 합이 가장 큰, smallest 레벨을 구하는 것이 문제다. 레벨 순회가 나오는 순간 bfs (breadth first search)를 떠올렸다. class Solution(object): def maxLevelSum(self, root): if not root: return 0 queue = [] queue.append(root) result_sum = root.val result_level = 1 curr_leve..

https://leetcode.com/problems/removing-stars-from-a-string 스택을 떠올리자. class Solution(object): def removeStars(self, s): sStack = [] for i in range(len(s)): if s[i] != "*": sStack.append(s[i]) else: if len(sStack) > 0: sStack.pop() return "".join(sStack)

operation 1을 보고서는 풀 수 있을 것 같았다. 두 개의 캐릭터를 스왑한다는 건 개수가 같으면 된다는 뜻이니까 말이다. operation 2에서 막혔다. 다른 사람의 풀이를 듣고 힌트를 얻었다. operation 2가 되려면 frequency를 카운트하면 된다.  word1 = "cabbba"가 있고, word2 = "abbccc"가 있다고 할 때word1에서 a는 2개, b는 3개, c는 1개가 나온다.그리고 2, 3, 1이라는 숫자가 각각 한 번씩 나온다.word2에서 a는 1개, b는 2개, c는 3개가 나온다.그리고 1, 2, 3이라는 숫자가 각각 한 번씩 나온다.그러므로 word1로부터 word2를 만들 수 있어서 답은 True이다.  풀이 방법 정리(1) word1과 word2의 알파..

https://leetcode.com/problems/equal-row-and-column-pairs/ 시간 초과가 났다.class Solution(object): def equalPairs(self, grid): row = [] col = [] for i in range(len(grid)): tempRow = grid[i] row.append(tempRow) for i in range(len(grid)): tempCol = [] for j in range(len(grid)): tempCol.append(grid[j][i]) ..

https://leetcode.com/problems/unique-number-of-occurrences hashmap을 이용해서 풀었다. class Solution(object): def uniqueOccurrences(self, arr): occurrence = [False * i for i in range(len(arr)+1)] occurDict = dict() for i in range(len(arr)): if arr[i] in occurDict: occurDict[arr[i]] += 1 else: occurDict[arr[i]] = 1 for key..