본문 바로가기

Medium174

[Leetcode] 1584. Min Cost to Connect All Points 문제 : https://leetcode.com/problems/min-cost-to-connect-all-points/ 최소신장트리, MST를 만드는 문제이다. 크루스칼 알고리즘을 사용했다. 각 point들을 정점으로 보고 모든 정점들간 간선을 연결하며 간선의 cost는 맨해튼 거리 수식으로 계산한다. 간선들을 cost 오름차순으로 정렬한뒤 DSU를 사용하여 사이클이 발생하는지 체크한다. 사이클이 발생하면 간선을 사용하지 못하고 사이클이 발생하지 않으면 cost를 정답변수에 더해준다. 시간복잡도는 정점의 수가 points 배열 크기이고 간선 수가 points^2이므로 간선들을 오름차순 정렬하는데 드는 O(간선 * log간선)이 된다. 소스코드 : https://github.com/fpdjsns/Algor.. 2022. 4. 26.
[Leetcode] 538. Convert BST to Greater Tree 문제 : https://leetcode.com/problems/convert-bst-to-greater-tree/ 이진 검색 트리(BST)가 입력으로 주어지면 BST의 모든 키가 원래 키보다 큰 모든 키의 합으로 변경하라. BST를 오른쪽 자식 노드 -> root 노드 -> 왼쪽 자식 노드 순으로 탐색하며 탐색한 노드들의 합을 저장하고 root 노드를 노드의 합으로 갱신하라. 오른쪽 자식 노드 탐색 합 갱신 root->val을 합으로 갱신 왼쪽 자식 노드 탐색 시간복잡도는 O(노드수) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/538.%20Convert%20BST%20to%20Greater%20Tree.cpp 2022. 4. 16.
[Leetcode] 731. My Calendar II 문제 : https://leetcode.com/problems/my-calendar-ii/ 부분합 문제. 정렬된 map을 만들고 map[start] + 1, map[end] -1을 갱신한다. ex) [[10, 20], [50, 60]] i 10 20 50 60 map[i] 1 -1 1 -1 부분합 1 0 1 0 map을 처음부터 탐색하면서 map[i]의 부분합을 구한다. 합을 구하면서 만약 3 이상인 경우가 있으면 map[start], map[end]를 이전 값으로 갱신한뒤 false를 반환한다. 탐색이 끝날때까지 3이상인 경우가 없으면 추가가 가능한 경우이므로 true를 반환한다. 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/med.. 2022. 4. 12.
[Leetcode] 31. Next Permutation 문제 : https://leetcode.com/problems/next-permutation/ 정수 배열이 있을 때 해당 배열의 요소들의 순서를 바꿔서 사전순 다음 시퀀스로 만들어라. 만일 불가능하다면 사전순 가장 작은 순서로 재배열해야한다. 예를 들어, arr = [2, 1, 3]이라면 사전순 다음 순서인 [2, 3, 1]로 재배열 시켜야한다. 전부 내림차순으로 정렬된 순열의 다음 사전순 배열은 이들을 역순한 것과 같다. 예를 들어, arr = [3, 2, 1]의 경우 다음 사전순 배열은 [1, 2, 3]이다. 내림차순된 배열의 다음 사전순 배열을 구하는 방법을 알았으니 내림차순 배열의 가장 앞에 있는 숫자를 해당 숫자보다 큰 수들보다 가장 작은 수로 바꾸면 다음 사전순 배열을 구할 수 있다. 말이 좀.. 2022. 4. 3.
[Leetcode] 287. Find the Duplicate Number 문제 : https://leetcode.com/problems/find-the-duplicate-number/ [1, n] 범위의 정수들로 이루어진 n+1 크기의 배열 nums가 주어진다. 이 배열엔 중복된 숫자가 하나만 존재파는데 중복된 숫자를 구해라. 단, nums 배열은 수정하지 않아야 하고 상수 크기의 추가 공간만 사용해야 한다. Floyd's cycle detection 으로 풀었다. nums 배열은 [1, n] 범위의 정수들로 이루어지고 중복된 숫자는 하나 밖에 없다는 조건을 이용해보자. index -> nums[index] 로 방향이 있는 간선을 연결하면 중복된 숫자가 하나가 존재하므로 순환이 발생하게 된다. 이 순환의 시작점이 중복된 숫자가 될 것이다. 순환의 시작점이 되는 지점(let, .. 2022. 4. 1.
[Leetcode] 74. Search a 2D Matrix 문제 : https://leetcode.com/problems/search-a-2d-matrix/ m x n 정수형 배열 matrix 가 있을 때, 아래 2가지 조건을 만족한다. - 정수는 각 행에서 왼쪽에서 오른쪽으로 오름차순 정렬되어 있다. - 각 행의 첫 번째 정수는 이전 행의 마지막 정수보다 크다. target 값이 주어질 때, matrix에서 target이 존재하는지 구해라. matrix 의 최상당 최우측에 있는 요소부터 탐색해나간다. 탐색중인 인덱스를 row, col 이라 하자. 만약 matrix[row][col]이 target과 같다면 target이 존재한다는 뜻이므로 true를 반환한다. 만약 matrix[row][col]이 target보다 크다면 col을 1 감소시킨다. 만약 matrix.. 2022. 3. 31.

티스토리툴바