1. Remove Duplicates from Sorted Array (No.0026)
문제 설명
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
해석
예제
코드
function removeDuplicates(nums: number[]): number {
let index = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] != nums[index])
nums[++index] = nums[i];
}
return ++index;
};🗒️코멘트
생각보다 오래 걸렸던 문제..접근 방식의 문제였다.
예시에서 보여줬던 대로 중복된 요소의 경우 "_"로 변경해서 풀려고 했으나 문제는 정렬이 제대로 되지 않아 예러를 표현해 줘서 한참 고민했다.
헌데 생각해보니 문제는 배열을 뱉어내는 것이 아니라 중복되지 않은 요소들을 앞으로 땡기고 그 숫자의 갯수를 반환하는 것이니 굳이 바꿔줄 필요가 없고 단순히 앞으로 옮겨지고 나서 옮긴 횟수+1 만큼만 반환하면 된다고 생각하니 문제가 쉽게 풀렸다.
2. Search Insert Position (No.0035)
문제 설명
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.
해석
오름차순으로 정렬된 숫자로 이루어진 배열과 목표 숫자가 주어졌을 때, 만약 그 목표 숫자가 배열 내에 있으면 그것의 인덱스를 반환하고 없으면 그 목표 숫자가 배열 내에 있다는 가정하에 그 숫자의 인덱스를 반환 해주세요.
단 이 문제를 풀 때는 반드시 시간 복잡도가 O(log n)이어야 합니다.
예제
코드
function searchInsert(nums: number[], target: number): number {
if(nums.includes(target)){
return nums.indexOf(target)
}
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
};🗒️코멘트
이진 탐색을 적용해서 푸는 문제.
확실히 이 전에 한 번 적용해 본 경험이 있다 보니깐 두 번째 적용은 확실히 쉬워졌고.
Binary Search의 시간 복잡도가 O(log n)이라는 것을 각인 시킬 수 있었다.
3. Count Lattice Points Inside a Circle (No.2249)
문제 설명
Given a 2D integer array circles where circles[i] = [xi, yi, ri] represents the center (xi, yi) and radius ri of the ith circle drawn on a grid, return the number of lattice points that are present inside at least one circle.
해석
데카르트 좌표에서 원을 나타내는 배열이 다음과 같이 주어지고 circles[i]=[xi,yi,ri], ith원의 중심이 (xi,yi) 반지름이 ri일 때 원 위에 있는 좌표들 중 정수로만 이어지는 좌표의 갯수를 반환하는 함수를 구현해주세요.
예제
코드
function countLatticePoints(circles: number[][]): number {
let maxX = 0, maxY = 0;
for (let [x, y, r] of circles) {
maxX = Math.max(maxX, x + r);
maxY = Math.max(maxY, y + r);
}
let count = 0;
for (let x = 0; x <= maxX; x++) {
for (let y = 0; y <= maxY; y++) {
for (let [xi, yi, ri] of circles) {
let distance = Math.sqrt((x - xi) ** 2 + (y - yi) ** 2);
if (distance <= ri) {
count++;
break;
}
}
}
}
return count;
};
🗒️코멘트
다른 사람에겐 모르겠으나 내게 있어 엄청 쉬운 문제였다.
쉽게 말해 x,y가 정수일 때, 원의 방정식을 만족하는 x,y의 좌표의 갯수를 구하는 문제였는데
만약 손으로 풀었으면 조금 귀찮았을 문제가 프로그래밍을 사용하니깐 금방 풀렸다.
원의 방정식은 다음과 같다.
