본문 바로가기

🏃 algorithm/leetcode93

LeetCode 226 - Invert Binary Tree (Easy) 문제 LeetCode - 226번 풀이 과정 주어진 이진 트리를 뒤집는 연산을 수행하는 문제입니다. 다른분들의 풀이법을 보니 level order traversal 을 사용하신 분들도 있었지만 저는 dfs 를 사용했습니다. 각 서브트리의 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리를 invert 해준 다음 해당 서브트리의 루트노드를 반환해줍니다. 이러한 재귀 호출을 반복하면 최종적으로 기존의 root 는 invert 된 트리가 됩니다. 코드 /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===.. 2021. 3. 3.

LeetCode 406 - Queue Reconstruction by Height (Medium) 문제 LeetCode - 406번 풀이 과정 각 사람들의 키 h 와 자신보다 앞에 서있는 사람들 중 자신보다 키가 큰 사람들의 수 n 이 주어질 때 조건에 맞도록 사람들을 나열하는 방법을 찾는 문제입니다. 따라서 우선 n 의 오름차순으로 정렬하며 n 이 같을 경우에는 h 가 증가하는 순으로 정렬합니다. 그리고 정렬된 사람들을 한명씩 자신의 위치를 찾아 삽입해주는 방식으로 진행합니다. 이때 n 을 만족시키면서 최대한 뒤에 위치하도록 설정해주도록 하는 탐욕적 선택 을 활용합니다. 코드 /** * @param {number[][]} people * @return {number[][]} */ var reconstructQueue = function (people) { const answer = []; peopl.. 2021. 3. 3.

LeetCode 54 - Spiral Matrix (Medium) 문제 LeetCode - 54번 풀이 과정 2차원 배열 을 이용한 구현 문제입니다. 배열의 움직임에서 규칙을 찾아 화전하는 시뮬레이션을 할 수도 있지만 좀 더 간단한 방법으로 DFS 를 활용하여 모든 위치를 탐색할 수 있습니다. 시작지점 (0, 0) 에서부터 오른쪽, 아래쪽, 왼쪽, 위쪽 순서대로 방향을 틀어가며 탐색합니다. 이때 방향을 전환하는 시점은 배열을 벗어나거나 이미 방문한 지점을 다시 방문하려고 할 때입니다. 이를 활용하면 다음과 같은 코드로 원하는 연산을 수행할 수 있습니다. 코드 /** * @param {number[][]} matrix * @return {number[]} */ var spiralOrder = function (matrix) { const m = matrix.length;.. 2021. 3. 3.

LeetCode 279 - Perfect Squares (Medium) 문제 LeetCode - 279번 풀이 과정 양의 정수 n 에 대해서 최소 개수의 완전 제곱수로 표현하는 방법을 찾는 문제입니다. 예를 들어 12 는 2의 제곱인 4 를 3번 더해서 만들 수 있습니다. 만약 구하고자 하는 수 n 을 이용해서 dp(n) = n을 완전 제곱수로 표현하기 위한 최소 개수 라고 한다면 다음과 같은 점화식을 세울 수 있습니다. dp(n) = min(dp(n-X)+1), 이때 X 는 n을 넘기지 않는 왼전 제곱 수 예를 들어 `dp(13)` 은 9를 완전 제곱수로 1개 선택하고 `dp(13-9) + 1 = dp(4) + 1` 과 같이 표현할 수 있는 것입니다. 따라서 위와 같이 점화식을 세워주면 `동적 계획법` 으로 문제를 해결할 수 있습니다. 코드 /** * @param {num.. 2021. 3. 3.

LeetCode 94 - Binary Tree Inorder Traversal (Medium) 문제 LeetCode - 94번 풀이 과정 이진 검색 트리의 중위 순회 를 구현하는 문제입니다. 재귀 호출 을 이용해서 왼쪽 서브트리, 서브 루트, 오른쪽 서브트리 순서로 방문해주면 됩니다. 코드 /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number[]} */ var inord.. 2021. 3. 3.

LeetCode 394 - Decode String (Medium) 문제 LeetCode - 394번 풀이 과정 문자열의 규칙에 따라 디코딩하여 원본 문자열을 찾는 문제입니다. [ 괄호 앞에는 반복할 숫자가 주어지기 때문에 스택 을 활용하여 문제를 해결하였습니다. 먼저 문자열의 각 문자를 순회하며 [ 와 ] 그리고 숫자 를 제외한 문자들은 그냥 push 해줍니다. 만약 숫자를 만날 경우에는 현재 스택의 top 이 숫자인지 판단하고 숫자라면 해당 숫자에 이어붙입니다. (두 자리수 이상이 있을 수 있기 때문에) 이후 ] 를 만나면 [ 가 발견될 때 까지 문자들을 pop 하고 [ 앞의 숫자만큼 repeat 해줍니다. 최종적으로 스택 에 남아있는 문자들을 모두 합쳐주면 우리가 찾는 원본 문자열이 됩니다. 코드 /** * @param {string} s * @return {str.. 2021. 3. 3.

이전 1 ··· 7 8 9 10 11 12 13 ··· 16 다음

티스토리툴바