99 Club 2기 | Java | Beginner
📥 35. Search Insert Position
🏷 관련 주제 : Array Binary Search
Easy
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
Constraints:
1 <= nums.length <= 10⁴-10⁴ <= nums[i] <= 10⁴numscontains distinct values sorted in ascending order.-10⁴ <= target <= 10⁴
Accepted 2.9M | Submissions 6.3M | Acceptance Rate 46.2%
✔ Solution with Binary Search
class Solution {
public int searchInsert(int[] nums, int target) {
int idxL = 0;
int idxR = nums.length - 1;
int pre = nums.length - 1;
if (target <= nums[0]) {
return 0;
}
while (idxL < idxR) {
if (nums[idxL] == target) {
return idxL;
}
if (nums[idxR] == target) {
return idxR;
}
if (nums[idxR] > target) {
pre = idxR;
idxR = (idxR + idxL) / 2;
} else if (nums[idxR] < target) {
idxL = idxR;
idxR = (idxL + pre) / 2;
}
}
return idxR + 1;
}
}채점 결과
💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍
📌 오늘 만난 문제
매개변수로 중복되지 않은 원소를 가진 정렬된 int배열 nums와 nums의 원소와 비교할 int target을 줄 때,
1) nums에 target과 같은 값의 원소가 있으면, 해당 인덱스를 반환
2) nums에 target과 같은 값의 원소가 없으면,target을 nums에 삽입하고 정렬하였을 때,target이 위치하게 되는 인덱스를 반환
즉, target을 nums에 삽입하고 중복 제거 및 정렬을 했을 때, target이 위치하게되는 인덱스를 반환하면 된다.
처음에 반복문을 통해 nums의 원소들을 탐색하여 문제를 풀었는데
온라인 코딩테스트에서 발표를 했더니 중요한 문제의 조건을 빠뜨린 것을 알게 되었다.
You must write an algorithm with O(log n) runtime complexity.
시간 복잡도를 계산하면서 코드를 작성했어야 하는데
내 코드의 시간 복잡도는 O(n)이어서 틀렸다고 하셨다.
예전부터 궁금했는데 시간복잡도... 어떻게 계산하는 거지?😗❓시간복잡도가 O(log n)이 나오려면 이분탐색을 해야한다고 하셨다.다시 코드를 짜 보아야겠다.
그리고 시간복잡도에 대해서도 알아보아야지!
(2024.06.26 수정)
Binary Search를 통해 문제를 다시 풀어보았다.
아직 알고리즘 복잡도 계산하는 방법을 정확히 모르지만
LeetCode에 Analyze Complexity 버튼으로 시간 복잡도와 메모리 복잡도를 계산해 주는 기능이 생겨서
시간 복잡도를 계산해 보았더니 O(logN)이라고 떴다.
미션 Clear!🥳
💬 무엇을 새롭게 알았는지
문제의 조건을 코드로 어떻게 나타내야 할 지 경우를 구체적으로 생각해 볼 수 있었다.
