본문 바로가기

Medium174

[Leetcode] 437. Path Sum III 문제 : https://leetcode.com/problems/path-sum-iii/ 이진 트리와 targetSum이 주어지면 경로의 노드들 값의 합이 targetSum과 같은 경로들의 수를 구하라. 백트래킹. 트리를 탐색하면서 탐색한 노드들의 val의 합의 개수를 map에 저장한다. 탐색하면서 이때까지의 합(sum)에서 targetSum을 뺀 값의 개수들의 합이 정답이 된다. [그림 1]에서는 테이블들의 빨간색 셸들이 이에 해당하여 정답은 3이 된다. 시간복잡도는 O(N). N = 노드 수 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/437.%20Path%20Sum%20III.cpp 2021. 10. 18.
[leetcode] 279. Perfect Squares 문제 : https://leetcode.com/problems/perfect-squares/ 정수 n이 입력으로 주어지면 완전제곱수들의 합으로 n을 만들 때 사용되는 완전제곱수들의 최소 개수를 반환하라. DP로 풀 수 있다. dp[i] = i를 만들 때 사용되는 완전제곱수들의 최소 개수 = dp[i - j*j] + 1 들 중 최소값 (j*j 2021. 10. 14.
[leetcode] 2028. Find Missing Observations 문제 : https://leetcode.com/problems/find-missing-observations/ 1~6까지 수가 새겨진 주사위가 (n+m)개가 있다. 모든 주사위를 굴린 값들 중 m개 주사위에 대한 정보를 가지고 있고 (n + m)개의 주사위의 평균값 mean 값도 알고 있다고 할 때, 가능한 n개의 주사위 결과를 반환하라. 만일 가능한 정답이 없다면 빈 배열을 반환하라. mean 값에 (n + m)을 곱하면 모든 주사위 값들을 더한 값이 된다. 이 값에 입력값으로 주어진 m개 주사위들의 값들을 뺀다면 n개의 주사위 눈들의 합(let, sum)이 된다. sum = mean * (n+m) - m개의 주사위 눈들의 합 = n개의 주사위 눈들의 합 sum / n 을 초기화 값으로 n 배열을 만들.. 2021. 10. 5.
[leetcode] 1328. Break a Palindrome 문제 : https://leetcode.com/problems/break-a-palindrome/ 소문자 영어로 이루어진 펠린드롬 문자열이 주어지면 한 문자만 다른 소문자 알파벳으로 변경하여 펠린드롬이 아닌 문자열로 만들고자 한다. 이 때, 사전순으로 가장 작은 문자열을 구하라. 만일 조건을 만족하는 변경 가능한 문자열이 없는 경우 빈 문자열을 반환하라. 펠린드롬이므로 1/2 개만 탐색해도 된다. (앞뒤 문자가 같으므로) 문자열이 홀수인 경우 가운데 문자는 펠린드롬 여부와 관계가 없으므로 변경하는 문자에서 제외시켜야 한다. -> 문자열 길이가 1인 경우 빈문자열을 반환한다. (어떤 문자를 바꿔도 펠린드롬이 되므로) 앞에서 1/2개의 문자들 중 ‘a’가 아닌 문자가 있으면 이를 ‘a’로 바꾼다. (앞에 문.. 2021. 9. 25.
[leetcode] 764. Largest Plus Sign 문제 : https://leetcode.com/problems/largest-plus-sign/ 왼쪽 -> 오른쪽. 오른쪽 -> 왼쪽. 위 -> 아래. 아래 -> 위 로 탐색하면서의 subSum을 모든 위치에서 구한다. (x,y)를 + 부호의 가운데 지점이라 할 때, (x,y)를 좌표로한 4가지 subSum들의 최소값이 + 부호의 최대 크기이다. 모든 (x,y)을 + 부호의 가운데라 가정하고 subSum들을 이용하여 + 부호의 크기들을 구했을 때 최대값이 정답이 된다. 시간복잡도는 O(N^2) 공간복잡도는 4가지 subSum들을 구해둬야 하기 때문에 O(4N^2). 소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/764.%2.. 2021. 9. 9.
[leetcode] 565. Array Nesting 문제 : https://leetcode.com/problems/array-nesting/ 길이가 n인 정수 배열 nums가 주어진다. nums는 [0, n-1] 범위의 겹치지 않는 숫자의 수열이다. s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]] ...} 라 할 때, s[k]의 모든 요소들의 중복이 있지 않아야 한다. 만들 수 있는 s[k]의 최대 길이를 구하라. nums 배열은 유니크한 숫자들로 이루어져있기 때문에 s[k]배열은 사이클이 만들어진다. 예를 들어, nums = {1, 2, 0, 3} 이라면 s[k]가 될 수 있는 배열들은 {1,2,0}, {3}이고 이들은 각각 사이클이 만들어진다. 즉 사이클이 만들어지는 s 배열을 만드는데 이 배열들 중 최장 .. 2021. 9. 3.

티스토리툴바