전체 글 (85) 썸네일형 리스트형 Leetcode: First Bad Version 문제설명 여러분은 프로덕 매니저(PM)이다. 여러분의 역할은 팀을 이끌어 새로운 제품을 개발해야 한다. 불행히도, 여러분의 최신 상품 퀄리티 체크에서 실패하고 말았다. 각각의 버전은 이전 버전에 기반을 두고 개발하였으므로 악성 버전 이후 모든 버전은 사용하지 못하는 버전이다. 여러분은 어떤 버전이 악성 버전인지 확인할 수 있도록 주어진 API는 isBadVersion(_ :Int)이다. API의 호출 수를 최소화하여 최초의 악성 버전을 찾아내라. Example 1 Input: n = 5, bad = 4 Output: 4 Explanation: call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true The.. Leetcode: Merge Sorted Array, 정렬된 배열 병합하기 문제설명 두 정렬된 배열이 주어졌을 때 배열을 병합하라 병합된 배열은 오름차순으로 정렬되어야 한다. 첫 번째 배열은 두 번째 배열만큼의 크기를 더 갖는다. 첫 번째 배열에 병합 결과를 넣는다. 문제풀이 가장 쉬운 방법은 첫 번째 배열에 두 번째 배열을 그대로 이어 붙이고 정렬하면 된다. 다만 O(log n)의 시간복잡도를 갖는다. 시간 복잡도를 O(N)로 풀려면, 첫번째 배열을 따로 복사하여 두 배열의 항목을 하나씩 비교하여 첫 번째 배열에 넣는다. func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) { let nums1Copy = Array(nums1) var p1 = 0, p2 = 0 for i in 0..= n || (p1 < .. Leetcode: Convert Sorted Array to Binary Search Tree, 정렬된 배열을 이진 탐색 트리로 변환 문제설명 오름차순으로 정렬된 배열이 주어졌을 때, 이것을 높이가 균형잡힌 이진 탐색 트리로 변환하라. 높이가 균형잡힌(height-balanced) 이진 탐색 트리는 모든 노드의 두 서브트리의 깊이 하나 이상 차이나면 안된다. 문제풀이 배열이 이미 정렬되어 있으므로, 배열의 중간의 값을 선택하여 preorder 방식으로 노드를 탐색하며 노드를 추가한다. 배열의 중앙의 값을 선택하고 다음 중앙의 값은 서브 배열은 왼쪽과 오른쪽에서 각각 구하면 된다. // MARK: - Answer func sortedArrayToBST(_ nums: [Int]) -> TreeNode? { return helper(arr: nums, 0, nums.count) } func helper(arr: [Int], _ left: I.. Leetcode: Binary Tree Level Order Traversal, 이진 트리 레벨 순서 순회 문제설명 이진트리가 주어졌을 때, 트리를 level 순서로 순회한 노드의 값들을 반환하라 순서는 왼쪽에서 오른쪽, 위에서 아래로가 된다. 문제풀이 이진 트리를 너비우선탐색(BFS)로 순회한다. 각 레벨마다 리스트에 리스트를 추가한다. 각 레벨은 어떻게 알 수 있을까? 큐에 남아있는 갯수만큼 다돌면 하나의 레벨을 순회한 것이다. // MARK: - Answer func levelOrder(_ root: TreeNode?) -> [[Int]] { var result = [[Int]]() guard let root = root else { return result } var queue = [TreeNode]() queue.append(root) var level = 0 while !queue.isEmpty {.. Leetcode: Symmetric Tree: 트리 대칭성 검증 문제설명 인자로 주어진 트리 노드의 대칭성을 검증하라 문제풀이 루트부터 왼쪽과 오른쪽 노드의 값이 같은지 검사한다. 자식 노드는 2개가 존재하므로 왼쪽과 오른쪽 노드를 검사해야 한다. // MARK: - Answer func isSymmetric(_ root: TreeNode?) -> Bool { return isSymmetricHelper(root, root) } func isSymmetricHelper(_ node1: TreeNode?, _ node2: TreeNode?) -> Bool { if node1 == nil && node2 == nil { return true } return node1?.val == node2?.val && isSymmetricHelper(node1?.left, node2.. Leetcode: Validate Binary Search Tree, 이진 탐색 트리 검증 문제설명 인자로 주어진 노드가 이진 탐색 트리인지 판별하라. 이진 탐색 트리는 왼쪽 서브 트리는 노드의 값(key)보다 작아야 한다. 오른쪽 서브 트리는 노드의 값(key)보다 커야 한다. 문제풀이 TreeNode와 최소값, 최대값을 하나의 타입에 캡슐화하기 위하여 BinarySearchTree를 임의로 정의하였다. 왼쪽 자식 노드를 탐색할 때는 부모인 현재 노드의 값이 최대값이 된다. 오른쪽 자식 노드를 탐색할 때는 부모인 현재 노드의 값이 최소값이 된다. // MARK: - Definition public class TreeNode { public var val: Int public var left: TreeNode? public var right: TreeNode? public init() { se.. List를 TreeNode로 변환하기 Swift에서 [1,2,3,4,nil,nil,5] 와 같이 표현된 리스트 리터럴을 TreeNode로 변환하려면 어떻게 구현해야할까? 먼저 리스트 원소의 규칙을 정해야 한다. 리스트의 순서는 트리의 노드가 순서대로 위치하는 순서다. 트리 노드의 정확한 순서를 지키기 위해 노드가 존재하지 않을 경우 nil로 표현해야한다. public class TreeNode { public var val: Int public var left: TreeNode? public var right: TreeNode? public init() { self.val = 0; self.left = nil; self.right = nil; } public init(_ val: Int) { self.val = val; self.left =.. Leetcode: Maximum Depth of Binary Tree, 이진 트리의 최대 깊이 문제설명 이진 트리가 주어졌을 때, 이진 트리의 루트 노드에서 리프 노드까지 가장 긴 경로의 길이를 구하라 문제풀이 stack과 Int 리스트를 사용한다. stack에 노드를 담는다. stack에서 노드를 꺼내고 자식 노드가 존재한다면, 다시 stack에 담는다. stack에 자식 노드를 추가할 때, depth를 저장한 리스트(depths)에 해당 노드의 깊이를 저장한다. stack과 depths의 아이템을 동시에 꺼내게 되는데, 이때 최대 depth를 반복하여 구한다. public class TreeNode { public var val: Int public var left: TreeNode? public var right: TreeNode? public init() { self.val = 0; sel.. 이전 1 2 3 4 5 6 7 8 ··· 11 다음 목록 더보기