본문 바로가기

🏃 algorithm/leetcode93

LeetCode 136 - Single Number (Easy) 문제 LeetCode - 104번 풀이 과정 하나의 숫자만 1개가 존재하고 나머지 숫자들은 2개씩 존재하는 배열에서 1개 존재하는 숫자를 single number 라고 했을 때 해당 수를 찾는 문제입니다. 문제 조건에서 O(N) 에 추가 메모리 공간을 사용하지 않고 구현하는 방법을 찾아야합니다. 이를 위해서 비트 연산자 중에서 xor 를 활용하도록 합니다. xor 연산은 서로 다른 비트에서만 1이고 나머지는 0이기 때문에 같은 숫자끼리 xor 을 하면 0이 됩니다. 따라서 single number 를 제외한 모든 수는 2개씩 존재하기 때문에 xor 결과 0이 되고 0 ^ single number = single number 로 구할 수 있습니다. 코드 /** * @param {number[]} nums .. 2021. 3. 3.

LeetCode 104 - Maximum Depth of Binary Tree (Easy) 문제 LeetCode - 104번 풀이 과정 이진 트리의 높이 를 구하는 문제입니다. 간단하게 DFS 를 수행해서 왼쪽 서브트리와 오른쪽 서브트리 중에서 높은 height 를 선택하도록 했습니다. 코드 /** * 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 maxD.. 2021. 3. 3.

LeetCode 102 - Binary Tree Level Order Traversal (Medium) 문제 LeetCode - 102번 풀이 과정 이진 트리의 level order 탐색을 구현하는 문제입니다. 대표적인 BFS 문제로 루트 노드를 기준으로 왼쪽과 오른쪽 서브트리의 루트 노드를 방문해주며 탐색을 수행하면 됩니다. 이때 주의할점은 문제 출력 형식이 level 에 있는 모든 노드를 하나로 묶어서 배열로 추가해야하므로 각각의 BFS 단계마다 현재 큐에 존재하는 모든 노드의 개수 만큼 루프를 돌며 자식 노드들을 탐색해야한다는 것입니다. 마치 백준의 토마토 문제와 비슷한 방식이죠. 이렇게 해야 현재 레벨에 존재하는 모든 노드를 함께 배열로 묶어줄 수 있습니다. 코드 /** * Definition for a binary tree node. * function TreeNode(val, left, righ.. 2021. 3. 3.

LeetCode 617 - Merge Two Binary Trees (Easy) 문제 LeetCode - 617번 풀이 과정 두 개의 이진 트리를 합치는 연산을 수행하는 문제입니다. 직관적으로 생각했을때는 쉬운거 같았는데 생각보다 어떤 방식으로 구현해야 명확할지 많은 고민을 했던 것 같습니다. 저는 merge 라는 함수를 재귀적으로 호출하여 문제를 해결하고자 했습니다. 우선 merge 의 기준이 되는 트리를 main, 나머지를 sub 로 나눈 다음 두 트리 모두 현재 루트 노드가 존재할 경우 main 에 값을 더했습니다. 다음 재귀호출 전에 먼저 서브트리가 존재하는지 확인하였고 두 트리 모두 각각 왼쪽 혹은 오른쪽 서브트리가 존재할때만 DFS 를 수행하고 그 외의 경우에는 별도의 처리를 해줬습니다. 여기서 별도의 처리란 main 의 왼쪽(오른쪽) 서브트리가 존재하지 않는데 sub 에.. 2021. 3. 3.

LeetCode 98 - Validate Binary Search Tree (Medium) 문제 LeetCode - 98번 풀이 과정 입력으로 주어진 트리가 이진 검색 트리 의 요구 사항에 맞는 구조를 가지고 있는지 판단하는 문제입니다. 이진 검색 트리 는 루트 노드가 왼쪽 서브트리의 모든 노드보다 커야하고 오른쪽 서브트리의 모든 노드보다 작아야합니다. 따라서 minMax 라는 함수를 통해 DFS 를 수행하며 현재 루트 노드를 기준으로 해당 서브트리의 가장 작은 값과 가장 큰 값을 반환하도록 합니다. 그런데 다 풀고나서 다른 사람들의 풀이법을 보니 그냥 중위 순회 를 한 다음 오름차순으로 되어있는지 확인하는 방법이 더 구현하기 쉽고 명확한 거 같습니다. 코드 /** * Definition for a binary tree node. * function TreeNode(val, left, righ.. 2021. 3. 3.

LeetCode 130 - Surrounded Regions (Medium) 문제 LeetCode - 130번 풀이 과정 X 로 둘러싸인 O 부분은 모두 뒤집었을 때 최종적으로 어떤 형태를 가진 board 가 되는지 구하는 문제입니다. 이때 한가지 주의할 점은 둘러싸는 테두리가 board 의 경계 위에 존재하면 안된다는 점입니다. BFS 를 사용하여 문제를 해결하였으며 현재 좌표에서 상하좌우로 이동했을 때 board 를 벗어나지 않는지 체크해서 조건을 검사해줬습니다. 문제를 풀면서 발생했던 이슈 중 하나는 ES6 의 Map 자료구조와 관련된 내용입니다. 처음에는 방문 좌표를 배열 키값으로 Map 에 저장하려고 했는데 테스트해보니까 키 값으로 배열을 사용할 경우 올바르게 동작하지 않았습니다. (만약 이렇게 하고 싶으면 배열을 다른 변수에 할당한 뒤 할당된 변수값을 활용해 키로 지정.. 2021. 3. 3.

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

티스토리툴바