개발자가 되고 싶은 준개발자

문제 16. 3Sum Closest [Medium] Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Example 1: Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). Constrai..

문제 7. Reverse Integer [Easy] Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0. Assume the environment does not allow you to store 64-bit integers (signed or unsigned). Example 1: Input: x = 123 Output: 321 Example 2: Input: x = -123 Output: -321 Example 3: Input: x = 12..

문제 Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and qas descendants (where we allow a node to be a descendant of itself).” BST가 주어질 때 가장 낮은 공통의 조상을 찾아라. 코드 문제 풀면서 주의 해야 했던 사항은 모든 노드가 uni..

문제 Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree. BST가 주어졌을 때 K번째로 작은 수를 찾아라. 코드 BST 문제의 경우 우선 순회를 어떤 식으로 할지 정해야 한다. 순회의 방식에는 inorder(left->root->right), postorder(left->rightt->root), preorder(root->left->right) 세가지의 경우가 있다. 이 문제에서는 K번째 수를 찾으라 했으니 순회를 했을때 정렬이 되는 방법을 택하는 게 좋을 듯 하다. 따라서 inorder를 택했다. # Definition for a binary tre..

문제 트리가 주어졌을 때, 트리가 Binary Search Tree인지 판별하라 코드 (Naive 버전) 트리가 BST인지를 판별하기 위해서는 1) 왼쪽 subtree, 오른쪽 subtree가 BST여야 하며, 2) root의 왼쪽 subtree에 있는 값들은 root보다 모두 작아야 하며, root의 오른쪽 subtree에 있는 값들은 root보다 모두 커야 한다. (재귀적으로 바닥까지 모든 subtree가) 따라서 직관적으로 tree를 모두 traverse하면서 이를 확인하는 코드를 짰다. # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = No..

문제 주어진 두 개의 트리가 같은 트리인지 확인해라. 풀이 이 문제는 각 하위 트리마다 모든 노드들이 같은지 확인해 주면 되므로 깊이우선탐색(DFS)으로 간단하게 풀 수 있다. 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isSameTree(self, p, q): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ if not p and no..

문제 레벨 별로 다른 순서(왼쪽->오른쪽, 오른쪽->왼쪽)로 이진 트리(Binary Tree)를 순회하라. 풀이 쉬울 줄 알았는데 생각보다 통과하기가 어려웠다. 기본적인 알고리즘은 이전 포스트인 이진 트리를 BFS(너비 우선 탐색) 방식으로 레벨별로 순회하는 알고리즘과 비슷하다. (june-coder.tistory.com/16?category=913762) [LeetCode] 102. Binary Tree Level Order Traversal 풀이 및 코드 문제 트리를 level 순으로 순회하여 각 레벨 별 노드의 값을 리턴한다. 풀이 이 문제는 트리를 level 순으로 순회하는 문제이기 때문에 BFS(너비 우선 탐색)가 적합하다. 트리의 루트부터 leaf까지 순� june-coder.tistory.c..

문제 트리를 level 순으로 순회하여 각 레벨 별 노드의 값을 리턴한다. 풀이 이 문제는 트리를 level 순으로 순회하는 문제이기 때문에 BFS(너비 우선 탐색)가 적합하다. 트리의 루트부터 leaf까지 순회를 하면서 한 레벨 씩 리스트에 담는다. 한 레벨 씩 리스트에 담기 위해서는 이전 레벨의 노드들의 리스트를 받아 해당 노들들의 left, right을 리스트에 넣으면 된다. 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class So..

문제 이진 트리가 주어질때, 중심을 기준으로 대칭인지를 결과로 리턴하라. 풀이 이 문제를 푸는 방법은 재귀(recursively)와 반복(iteratively) 2가지 방법이 있다. 우선 재귀로 푸는 방법을 살펴보자. 보통 Tree 문제를 재귀로 풀때에는 root를 확인하고, 왼쪽 서브트리와 오른쪽 서브트리를 확인하는 방식으로 구현한다. 이 문제도 똑같은 방법으로 해결 가능하다. 단, 주의할 점은 대칭임을 확인하기 위해서는 왼쪽 서브트리와 오른쪽 서브트리를 반대로 비교해야 한다. 즉 두 서브트리의 root가 같은지 확인하고, 왼쪽 서브트리의 left가 오른쪽 서브트리의 right가 같은지, 왼쪽 서브트리의 right이 오른쪽 서브트리의 leftt가 같은지 확인하면 된다. 같은 풀이를 iterative하게..

문제 문자열이 주어지면 이를 키를 이용하여 해독하는 방법의 수를 리턴하는 문제이다. 해독하기 위한 키는 다음과 같다. 'A' -> 1 'B' -> 2 ... 'Z' -> 26 예) "12"는 "AB"나 "L"로 해독될 수 있다. (2가지 방법) "123"은 "ABC"나 "LC"나 "AW"로 해독될 수 있다. (3가지 방법) 풀이 이번 코드는 길이는 짧으나 직관적이지는 않은 것 같다. (더 좋은 방법이 떠오르면 추후에 수정해야 겠다!) 주어진 문자열을 순회하면서 1) 해당 인덱스(i)의 숫자가 1~9의 숫자인지 확인한다. 맞다면 i까지의 방법 개수는 i-1까지의 방법 개수와 같다. (이 문장이 이해가 가지 않는다면 예로 "89"를 생각해 보자. i가 1인 상황을 가정한다. "9"는 1~9의 숫자이므로 1번..