one line of code at a time

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ 문제 오름차순으로 정렬된 배열이 있을 때 두 개의 숫자를 합했을 때의 값이 target이 되는 그 두 숫자의 index를 반환하는 문제이다. Sol 1) 이진탐색 나는 이진탐색을 이용해 이 문제를 풀었다. numbers라는 배열에서 숫자 하나씩 iterate 하면서 다른 짝꿍을 찾는 것이다.예를 들어, numbers = [2, 7, 11, 15] 라는 배열과 target = 9가 있을 때우선 2를 본다. 그러면 새로운 target은 9 - 2인 7이 된다. 7을 찾으면 두 숫자의 합이 target이 된다.그리고 이 7을 찾을 때 이진탐색을 이용한다.  class Solution: def..

https://leetcode.com/problems/minimize-maximum-of-array/ nums = [3, 7, 1, 6]subproblem.3만 바라보면, 3이 우리의 initial result이다. 3보다 더 작아질 수는 없기 때문이다. 이제 3과 7을 보자. operation을 한 번 하면 [4, 6]이 된다. 그 다음 [5, 5] 가 된다. [4, 6]의 최댓값은 6이고, [5, 5]의 최댓값은 5이다.여기서 최댓값이 5보다 더 작아질 수 있을까?operation을 한 번 더 하면 [6, 4]가 된다. 최댓값은 6이다. 즉, 5보다 더 작아질 수는 없다. 그럼 result 값을 5로 업데이트 하면 될까?우리의 목표는 값을 evenly distribute 하는 것이다.그렇기 때문에 평..

https://leetcode.com/problems/my-calendar-i/ double booking이 아니면 캘린더에 이벤트를 집어넣을 수 있고 True를 반환하고, double booking 이면 False를 반환해야 한다. MyCalender 라는 클래스를 완성하고, book 메서드를 구현해야 한다.double booking은 어떤 이벤트가 이미 캘린더에 있을 때 그 이벤트와 시간이 겹치면 double booking이다. 시간이 겹친다는 것을 표현하면, 후보 이벤트가 이미 캘린더 안에 있는 이벤트의 start와 end 시간 사이에 있으면 안 된다. class MyCalendar(object): def __init__(self): self.dates = [] def boo..

https://leetcode.com/problems/non-decreasing-array/ 배열이 주어졌을 때 최대 1개의 숫자를 바꿔서 오름차순 정렬되게 배열을 만들 수 있는지 묻는 문제다.오름차순 정렬을 할 수 있으면 True를, 그렇지 않으면 False를 반환한다. 여기서 헷갈렸던 걸 2개의 테스트케이스를 가지고 설명할 수 있다.nums1 = [3, 4, 2, 3]nums2 = [-1, 4, 2, 3]첫 번째 배열은 한 번만 바꿔서 오름차순 배열을 만들 수 없고,두 번째 배열은 그렇게 할 수 있다. i 번째 element가 i+1 번째 element보다 크면, 숫자를 바꿔줘야 한다.그런데 2가지 경우가 있다.(1) 첫 번째 배열처럼 i-1 번째가 i+1 보다 클 때와 (2) 두 번째 배열처럼  i..

https://leetcode.com/problems/convert-bst-to-greater-tree/https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/ 이진 탐색 트리 (binary search tree, BST)가 있을 때그 노드의 값과 그 노드보다 큰 값을 모두 더한 값으로 노드를 다시 채워 넣는 문제이다. DFS를 하면 된다는 건 감이 왔지만, 코드를 짜지 못했다는 게 문제다. 전위 순회 (preorder), 중위 순회 (inorder), 후위 순회 (post order)의 순서는 각각 VLR, LVR, LRV 이다.(V는 부모, L은 왼쪽 자식, R은 오른쪽 자식) 이 문제는 inorder traversal을 revers..

https://leetcode.com/problems/reorder-list/ 연결리스트를 이런 순서로 reorder 해야 한다.  연결리스트를 반으로 나눴을 때 첫 번째 파트는 그대로 방향을 유지하면 된다.그런데 두 번째 파트는 맨 마지막에 포인터를 두고 끝에서 앞쪽으로, 즉 reverse 시킬 수 있다.그렇게 alternating 시키면서 두 연결리스트를 merge 시키면 된다. 그런데 중간 지점을 어떻게 찾을 것인가?slow pointer와 fast pointer를 사용하면 된다. 그 다음에 새로운 연결 리스트를 만들지 않고, 원래 연결 리스트를 사용해서 만들 수 있다.그러면 공간 복잡도는 O(1)이 된다.이 때 가장 첫 번째 노드에서 1st 포인터가 시작되고, 가장 끝 노드에서 2nd 포인터가 시..

https://leetcode.com/problems/lexicographical-numbers lexicographical order로 정렬하라는 문제다. 예시를 보면 딱 알 수 있다.n = 13 이면, 정렬된 output은 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9] 이다. DFS로 풀 수 있다.  이 솔루션의 time complexity는 노드를 한 번씩 방문하니까 O(n)이다. class Solution(object): def lexicalOrder(self, n): res = [] def dfs(curr): # base case if curr > n: return ..

https://leetcode.com/problems/find-the-length-of-the-longest-common-prefix/ 문제: 두 개의 배열이 있을 때 arr1에서의 원소, arr2에서의 원소의 가장 긴 common prefix의 길이를 구하는 문제다. class Solution(object): def longestCommonPrefix(self, arr1, arr2): arr2Set = set() arr2Pre = list(set(arr2)) arr1Pre = list(set(arr1)) # make hashset for num in arr2Pre: numStr = str(num) # "1000" ..

https://leetcode.com/problems/linked-list-cycle/class Solution(object): def hasCycle(self, head): if not head: return False visitSet = set() while head.next: visitSet.add(head) if head.next in visitSet: return True head = head.next return False 방문 배열을 만들어서 연결 리스트에서 방문한 노드를 저장한다.다음 노드가 있을 때까지 반복하는데 그 다음 노드가 ..

https://leetcode.com/problems/keys-and-rooms/ class Solution: def canVisitAllRooms(self, rooms: List[List[int]]) -> bool: keySet = set() keySet.add(0) visitedRooms = set() def dfs(currRoom, keySet): if currRoom not in keySet: return False visitedRooms.add(currRoom) for k in rooms[currRoom]: if k..