one line of code at a time

https://leetcode.com/problems/kth-largest-element-in-an-array/description/ 정수로 되어 있는 배열 nums에서 k번째로 큰 숫자를 찾는 것이다. "정렬" 알고리즘을 사용하지 않고! 내가 푼 방법은 heap을 사용했는데 max heap을 사용했다. max heap을 써서 k-1번 heappop(nums)을 해주고, 그 힙에서 0번째 값에 (-1)을 곱해서 리턴해주었다. class Solution(object): def findKthLargest(self, nums, k): nums = [(-1) * i for i in nums] heapq.heapify(nums) for _ in range(k-1): ..

https://leetcode.com/problems/kth-largest-element-in-a-stream/description/ stream 안에서 k번째 큰 숫자를 찾는 문제인데 stream이라는 건 숫자를 계속해서 추가할 수 있다는 의미다. 이걸 효율적으로 찾을 수 있도록 하는 자료구조가 있는가?있다. 바로 Min Heap of size K. Min heap에서 log(N) 만에 add or pop 할 수 있다.최솟값은 O(1) 만에 찾을 수 있다. Max Heap 대신에 Min heap을 사용하는 이유는? 여기서는 값을 remove 하지 않고 추가만 한다. [4, 5, 8, 2]라는 숫자 배열이 있고 k가 3일 때 while the size of the loop is greater than k..

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/ character가 반복되지 않는 가장 긴 substring의 길이를 구하는 문제다. left pointer와 right pointer를 이용했다. 처음에는 lp와 rp가 당연히 0 index를 가리키고 있다.이제 string s의 character를 하나씩 훑고 지나갈 것이다.  s = "tmmzuxt"라는 string이 있다고 하자.rp 가 처음에 0이므로 s[rp] = "t"이다. character를 담는 딕셔너리를 만들어줬다. 딕셔너리의 key는 character이고, value는 right pointer의 index다.딕셔너리에 우선 c..

prefix를 담은 tree를 trie ('트라이')라고 한다. 자동 완성이나 스펠링 체크를 할 때 쓰이는 알고리즘이다. 트라이를 구현해보자. class TrieNode: def __init__(self): self.children = {} self.endOfWord = Falseclass Trie(object): def __init__(self): self.root = TrieNode() def insert(self, word): cur = self.root for c in word: if c not in cur.children: # 만약 c가 자식 노드에 없다면 cur.chil..

이진트리에서 맨 오른쪽에 있는 노드의 값만 리턴하는 문제이다.https://leetcode.com/problems/binary-tree-right-side-view/description/  각 레벨에서 맨 오른쪽에 있는 노드들인 것을 알 수 있다.BFS로 레벨 순회를 하면서 맨 마지막 인덱스의 값(val)을 배열에 넣어줄 것이다. class Solution(object): def rightSideView(self, root): result = [] if not root: return result queue = [root] while queue: level = len(queue) ..

내가 좋아하는 그래프 문제. 왼쪽 위에는 태평양이 있고, 오른쪽 아래에는 대서양이 있다.이 둘을 건널 수 있는 좌표값들을 리스트에 반환하는 문제다. 태평양과 대서양을 건널 수 있는 좌표는 그 주변에 있는 섬들의 해수면 높이(sea level)보다 크거나 같아야 한다.즉, 이웃하는 셀들의 해수면 높이가 내가 위치한 셀의 해수면 높이보다 작거나 같아야 한다.  어떻게 해서 꾸역꾸역 푼 나의 코드는 다음과 같다. class Solution(object): def isPacific(self, r, c): if r == 0 and c == 0: return True elif r == 0 or c == 0: return True el..

배열이 주어졌을 때 이 배열의 subarray 중에서 가장 큰 합을 가지는 subarray의 합을 구하는 문제다.  [8, -1, -1, -1, -1] 이런 배열도 있을 수 있겠고, 문제에서 예제로 주어진 건 3가지 배열이다. nums = [-2,1,-3,4,-1,2,1,-5,4]nums = [1]nums = [5,4,-1,7,8] 그래서 1개씩만 element를 볼 때, 2개, 3개, ..., len(nums)개를 한 꺼번에 볼 때 합을 구하도록 만들었다. maximum = nums[0]for k in range(1, len(nums)+1): # k = 1, 2, 3, 4, 5 for i in range(len(nums)+1-k): # 5 + 1 - 1 = 5 # i = 0, 1, 2, 3, 4 ..

정렬된 배열에서 최솟값을 찾는 문제다. 그런데 완전히 정렬된 배열은 아니다. rotate되지 않았으면 가지런히 정렬된 배열이었겠지만, 한 번 rotated 되었기 때문에 정렬된 2개의 덩어리가 있다. 여기서 O(logn) 만에 최솟값을 찾아야 한다. 정렬과 주어진 시간 복잡도를 봤을 때 이진탐색을 써야 한다. 그런데 문제도 살짝 달라졌으니 이진 탐색 코드도 살짝 달라져야겠다. left pointer, right pointer, mid pointer를 둔다.mid pointer와 left pointer를 비교한다. 그래서 왼쪽이 가운데보다 작다면, (1) 이건 한 쪽이 정렬된 배열이니까 가장 왼쪽에 있는 값을 최솟값으로 두고, (2) left pointer를 mid+1로 옮겨서 오른쪽 배열을 봐야 한다. ..

자신의 인덱스를 제외한 나머지 숫자들의 곱을 계산하는 문제이다.O(n)으로 작성해야 하며 나눗셈은 쓸 수 없다. 첫 번째 방법, prefix와 postfix 배열 사용하기  prefix = [0] * len(nums)postfix = [0] * len(nums)output = [0] * len(nums)for i in range(len(nums)): if i > 0: prefix[i] = prefix[i-1] * nums[i] else: prefix[i] = nums[i]for i in range(len(nums)-1, -1, -1): # i = 3, 2, 1, 0 if i len(nums)-1: output[i] = prefix[i-1] el..

트리의 최대 높이 구하는 문제이다.root에서 자식 노드까지 쭉 이어지는 노드를 카운트해서 가장 큰 것이 트리의 최대 높이가 된다. 첫 번째 방법: DFS (recursion)maximum height = 1 + max(dfs(왼쪽 서브트리) + dfs(오른쪽 서브트리)) class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: # root is null -> return return 0 return 1 + max(self.maxDepth(root.left), s..