2022년 12월 25일 일요일 - 메리 크리스마스~~
오늘 올려볼 문제는 2389번 Longest Subsequence With Limited Sum 이라는 문제이다.
사진을 클릭하면 해당 문제로 이동합니다.
오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.
이진 탐색 변형을 익힌다고 생각보다 오래걸렸음..
입력
사진에서도 볼 수 있듯이 int 배열 2개가 입력으로 들어온다.
풀이 및 코드
nums의 subsequence 중에 합이 queries[i] 보다 같거나 작은 subsequence 중 가장 긴 길이를 구해서 배열로 리턴하는 문제이다.
오늘은 처음부터 정답을 생각해냈다.
nums를 정렬하고 그 index까지의 합을 구해서 저장한다. ex) nums = {1,2,3,4} -> {1,3,6,10}
이후 이진 탐색을 통해서 queries[i]보다 같거나 작은 값을 nums에서 이진 탐색으로 찾는다.
이제 코드를 봐보자!
풀이코드
class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
var result = new int[queries.length];
Arrays.sort(nums);
for(int i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1];
}
for(int i = 0; i < result.length; i++) {
result[i] = find(nums, queries[i]);
}
return result;
}
public int find(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}
제출 화면
이진 탐색 변형에 좀 약한걸 알고있었어서 익힐겸 고민을 좀 했더니 이지문제에 생각보다 많은 시간을 썼다.
하지만 충분히 익힌 것 같으니 도움이 된 것 같다!
내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.
'LeetCode 문제 풀이' 카테고리의 다른 글
[LeetCode] 2279번 Maximum Bags With Full Capacity of Rocks 문제를 풀어보았다. (ft. java) (0) | 2022.12.27 |
---|---|
[LeetCode] 55번 Jump Game 문제를 풀어보았다. (ft. java) (0) | 2022.12.26 |
[LeetCode] 739번 Daily Temperatures 문제를 풀어보았다. (ft. java) (0) | 2022.12.18 |
[LeetCode] 150번 Evaluate Reverse Polish Notation 문제를 풀어보았다. (ft. java) (0) | 2022.12.17 |
[LeetCode] 931번 Minimum Falling Path Sum 문제를 풀어보았다. (ft. java) (0) | 2022.12.13 |