알고리즘 문제408 [Leetcode] 902. Numbers At Most N Given Digit Set 문제 : https://leetcode.com/problems/numbers-at-most-n-given-digit-set/ 내림차순으로 정렬된 숫자 배열 digits와 정수 n이 주어진다. digits 배열의 숫자는 원하는 만큼 재사용 가능하다. digits 수들을 이용하여 숫자를 만들 때, 정수 n보다 작거나 같은 정수들의 갯수를 구하라. 예시를 직접 풀면서 알아보자. digits = ["1", "3", "5"], n = "355" 입력 값이 위와 같을 때, 일의 자리(x), 십의 자리(xx) 수들은 모두 정답에 포함된다. 따라서 이들 개수는 정답에 미리 더해둔다. x 에 digits 들 중 어느 숫자가 와도 상관없으므로 조합을 생각하면 각 자리에 3개의 수가 올 수 있으므로 일의 자리의 경우의 수는.. 2021. 12. 19. [Leetcode] 147. Insertion Sort List 문제 : https://leetcode.com/problems/insertion-sort-list/ 단일 linked list의 헤드가 주어질 때 삽입 정렬을 이용하여 이들을 정렬한뒤 정렬된 linked list의 헤드를 반환하라. 정렬된 링크드 리스트의 헤드를 저장하기 위해 ListNode를 하나 만들고 이 노드의 주소값을 newHead 변수에 저장한다. 원본 head의 노드를 처음부터 하나씩 정렬시켜야 하므로 앞에있는 노드부터 하나씩 탐색하며 newHead를 헤드로 하는 링크드 리스트의 적절한 위치에 연결해준다. 탐색하는 노드의 포인트를 originNode라 하자. 정렬된 링크드 리스트의 적절한 위치를 찾을 때 노드를 적절한 위치에 넣기 위해서는 해당 노드의 앞에 위치하는 노드를 알아야 한다. 예를 .. 2021. 12. 15. [Leetcode] 1446. Consecutive Characters 문제 : https://leetcode.com/problems/consecutive-characters/ 이전 문자와 동일한지 체크하며 동일하면 cnt 변수를 +1, 아니면 1로 갱신하며 탐색하며 갱신된 cnt들 중 최대값이 정답이 된다. 시간복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1446.%20Consecutive%20Characters.cpp 2021. 12. 13. [Leetcode] 1306. Jump Game III 문제 : https://leetcode.com/problems/jump-game-iii/ 음이 아닌 정수 arr 배열과 시작 인덱스 start가 주어진다. 인덱스 i에 있을 때 i+arr[i], i-arr[i] 인덱스로 점프할 수 있다고 할 때 값이 0인 인덱스에 도달할 수 있는지를 구하라. i번째 인덱스를 방문한 적이 있는지를 저장하는 배열을 하나 만들고 시작 인덱스 start부터 i+arr[i], i-arr[i] 인덱스 위치로 탐색하며 이미 방문한 적이 있다면 더 이상 탐색하지 않고 탐색한적이 없으면 방문여부를 true로 갱신한 다음 해당 값이 0이면 true를 반환한다. 해당 값이 0이 아닌 경우 i+arr[i], i-arr[i]가 배열 arr 범위 내부이며 방문한 적 없는 인덱스인 경우 탐색을 이.. 2021. 12. 9. [Leetcode] 563. Binary Tree Tilt 문제 : https://leetcode.com/problems/binary-tree-tilt/ 이진 트리 루트가 주어지면 모든 트리 노드의 기울기 합을 구하라. 트리 노드의 기울기는 모든 왼쪽 하위트리 노드들의 합, 모든 오른쪽 하위 트리 노드들의 합들 차이의 절대값이다. 만일 하위트리가 없으면 합을 0으로 본다. 정답 전역변수를 하나 두고 왼쪽, 오른쪽 하위트리를 탐색하며 합들을 구한 뒤, 왼쪽 오른쪽 노드들의 합 차이의 절대값을 정답 변수에 더해나간다. 그리고 왼쪽, 오른쪽 자식 노드들의 합 + 현재 노드의 val을 더한 값을 반환한다. 정답 = 0 func getSum(node) { if(node == NULL) return 0 left = getSum(node->left) right = getSu.. 2021. 12. 8. [Leetcode] 1290. Convert Binary Number in a Linked List to Integer 문제 : https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/ 0 혹은 1 값을 가지는 노드로 이루어진 linked list가 주어진다. 이를 10진수 값으로 반환하라. 초기값이 0인 정답 변수를 두고 head 노드에서 링크드리스트를 모두 탐색하면서 (2 x 정답 + 탐색노드.val) 로 정답 변수를 갱신해나간다. 시간복잡도는 O(N) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/1290.%20Convert%20Binary%20Number%20in%20a%20Linked%20List%20to%20Integer.cpp 2021. 12. 7. 이전 1 ··· 9 10 11 12 13 14 15 ··· 68 다음