Medium174 [Leetcode] 799. Champagne Tower 문제 : https://leetcode.com/problems/champagne-tower/ DP로 풀었다. dp[row][glass] = row 행의 glass 번째 그릇의 남는 샴페인 양. = (dp[row-1][glass] + dp[row-1][glass+1]) % 1 dp[0][0] = poured로 갱신 후 아래 수도코드를 진행한다. for(int row=0; row 2022. 3. 5. [Leetcode] 413. Arithmetic Slices 문제 : https://leetcode.com/problems/arithmetic-slices/ nums 배열을 탐색하면서 탐색 중인 nums[i] 를 포함하는 정답가능한 subarrays 수를 정답에 더해나간다. nums[i]를 포함하는 정답가능한 subarrays 수를 구하기 위해, nums[i], nums[i-1] 두 요소간 차이와 동일한 nums 요소 수를 cnt 변수에 저장한다. nums[i]-nums[i-1]이 nums[i-1]-nums[i-2] 와 동일하다면 cnt + 1, 동일하지 않다면 cnt를 2(i-1, i)로 갱신한다. nums[i]를 포함하는 정답가능한 subarrays 수는 cnt-2이다. 정답가능 하위배열은 앞에서부터 요소를 하나씩 삭제해가며 최소 3개이상의 요소만 있으면 정답.. 2022. 3. 3. [Leetcode] 662. Maximum Width of Binary Tree 문제 : https://leetcode.com/problems/maximum-width-of-binary-tree/ 이진 트리의 루트가 주어지면 트리의 최대 너비를 구하라. 최대 너비는 모든 레벨 중 최대 너비이며, 한 레벨의 너비는 가장 왼쪽 노드와 가장 오른쪽 노드의 길이이다. 만약 노드들 사이에 null 노드가 존재한다면 null 노드도 길이에 포함시킨다. 이진트리의 인덱스를 구해보면 위와 같다. 특정 노드의 왼쪽 자식 노드의 인덱스는 2 x 인덱스. 오른쪽 자식 노드의 인덱스는 2 x 인덱스 + 1 이다. 이를 이용하여 루트 노드부터 자식 노드들을 탐색해가며 각 레벨에서 가장 왼쪽에 존재하는 노드와 가장 오른쪽에 존재하는 노드의 인덱스 차이가 너비가 된다. 구한 너비들 중 최대값이 정답이 된다. .. 2022. 2. 27. [Leetcode] 1781. Sum of Beauty of All Substrings 문제 : https://leetcode.com/problems/sum-of-beauty-of-all-substrings/ 문자열의 beauty는 가장 자주 사용되는 문자와 가장 자주 사용되지 않는 문자 사이의 빈도 차이이다. 문자열 s가 주어졌을 때 모든 하위 문자열의 beauty 합을 구해라. s.length가 500 이므로 완탐을 돌린다. 2차원 반복문을 돌려서 s[start~end]에서 문자의 등장횟수를 갱신하며 탐색당시의 beauty 값을 구해 정답에 더해나간다. for start = [0, |s|) 문자의 등장횟수를 저장하는 map 갱신 for end = [start, |s|) s[end] 횟수 + 1 등장횟수 map을 탐색하며 최대등장횟수, 최소등장횟수를 구해서 차이를 정답에 더한다. 시간복잡.. 2022. 2. 24. [Leetcode] 454. 4Sum II 문제 : https://leetcode.com/problems/4sum-ii/ 크기가 n인 4개의 정수 배열 nums1, nums2, nums3, nums4가 있다. nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 을 만족하는 튜플(i,j,k,l)의 수를 구하라. map을 이용하여 nums1 + nums2 값을 key, 개수를 value에 저장한다. nums3 + nums4 요소들을 구하면서 map 에 -1 x (nums3 + nums4)를 key 값으로 하는 요소가 있는지 확인하고 있다면 value를 정답에 더해준다. 시간 복잡도는 O(N^2) 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medi.. 2022. 2. 3. [Leetcode] 1305. All Elements in Two Binary Search Trees 문제 : https://leetcode.com/problems/all-elements-in-two-binary-search-trees/ 두 개의 bst 트리의 루트 노드들이 입력으로 주어질 때, 두 개의 트리들이 가지는 요소들의 오름차순 정렬된 리스트를 구해라. 중위순회 로 두 개의 bst를 각각 탐색하여 정렬된 2개의 리스트를 만든다. 두 개의 리스트를 앞에서부터 탐색하면서 탐색 중인 요소들 중 작은 값을 먼저 정답 배열에 추가하는 식으로 정답 배열을 만들어나간다. 시간복잡도는 두 개의 bst의 노드 개수를 각각 N, M 이라 한다면 O(N + M). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1305.%20All%2.. 2022. 1. 26. 이전 1 ··· 3 4 5 6 7 8 9 ··· 29 다음
