본문 바로가기

algorithm63

Leetcode209.MinimumSizeSubarraySum 문제209. Minimum Size Subarray Sum양수 nums (int array), 양수 target 이 주어짐nums 부분배열의 합이 크거나 같은 subarray (연속적) min length 구하기풀이 (window)window 생각하고 포인터를 이동시키면서 subarray length 구하면 됨자세한 설명은 아래 주석source /** * 1. 문제 * - 양수 nums 주어짐 * - 양수 target 도 주어짐 * - 부분배열의 합이 크거나 같은 minimal length 였네. * - 연속된 sequence 맞네 * - 여러개가 나올 수 있음. 최소 length 를 구해야함 * - 답이 없으면 0 을 retu.. 2024. 5. 14.
Leetcode167.Two Sum II - Input Array Is Sorted 소스코드문제167. Two Sum II - Input Array Is Sortednumbers int array 가 주어지며, numbers 중 2개의 숫자를 더해 target 을 만족풀이 (brute-force)시간복잡도 O (n 제곱) for 2번 돌리면서 순회 target 보다 크면 stop풀이(공간 사용)Map 에 저장을 한다for loop 순회하면서 target - numbers[i] = map 에 있는지 체크이러면 시간복잡도 O(n), 공간복잡도 또한 O(n)풀이 (two Pointer)양끝에서 시작양끝의 합이 target 보다 크면 right--양끝의 합이 target 보다 작으면 left++이렇게 진행하면 결국 원하는 값을 찾게됨시간복잡도 O(n) / 공간복잡도 O(1)소스 /**.. 2024. 5. 6.
Leetcode80.RemoveDuplicatesFromSortedArrayII 소스코드문제80. RemoveDuplicatesFromSortedArrayII풀이 (brute-force)문제는 array 의 중복을 제거하는 것인데 최대 2개까지 허용중복 제거된 array 의 length 를 return 하고 중복 제거 후, nums 배열을 바꿔줘야함시간복잡도 O(n 제곱)순회하면서 앞뒤로 비교값이 같으면 2개까지 중복허용하고, 3개 이상 부터는 버림값이 틀리면 nums 를 수정요약 : nums 배열을 바꿔주면서 nums.length 를 구하는 것. 같으면 nums 배열 유지. 단, equalCount = 2 까지, 다르면 nums 채워넣어야 함 /** * 1, 1, 1, 2, 2 ,3 * 1 고정 * 1, 1 eq = 2 * 1, 1, 1 은 eq .. 2024. 5. 1.
Leetcode713.SubarrayProductLessThanK 소스코드 문제 713. SubarrayProductLessThanK 풀이 (brute-force) 시간복잡도 O(n 제곱) 아래 문제 풀 때, 실수는 end 를 원위치 시키는 것 연속적이고 부분배열을 구하는거면 Window 를 고려 /** * 10 count 1 * 10 * 5 -> count 2 * 10 * 5 * 2 멈춤 * 5 -> count 3 * 5 * 2 -> count 4 * 5 * 2 * 6 -> count 5 * 2 -> count 6 * 2 * 6 -> 7 * 6 -> 8 * * brute-force * 시간복잡도 O(n 제곱) */ fun numSubarrayProductLessThanKBruteForce(nums: IntArray, k: Int): Int { var .. 2024. 4. 20.

티스토리툴바