1. Binary Search (No.0704)
문제 설명
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
해석
우선, 숫자로 이루어진 오름차순의 배열과 목표 정수가 주어졌을 때, 만약 그 목표 정수가 배열내에 있으면 그 인덱스 값을 없으면 -1을 반환하는 함수를 구현해주세요. 이 때 함수의 시간복잡도는 O(log n)이어야 합니다.
예제
코드
//첫 번째 풀이 법
function search(nums: number[], target: number): number {
return nums.indexOf(target)
};
//Binary Search를 사용한 풀이법
function search(nums: number[], target: number): number {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const 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 -1;
};🗒️코멘트
우선 이진 탐색을 쓰지 않고 가장 직관적인 방법인 Array.indexOf 메서드를 사용하였다.
이 메서드를 사용하게 되면 굳이 경우를 나누지 않아도 -1을 유도할 수 있어 편했지만 문제는 이진 탐색을 강요했기에 이진 탐색을 적용하였다.
이진 탐색을 적용하게 되면 indexOf는 O(n)을 가지기 대문에 당연히 시간 복잡도는 줄어들게 되지만 한 가지 의문이 들었다.
1번의 경우, 코드의 양이 2번 답안에 비해 상대적으로 적고 코드가 간결하다.
과연 이진 탐색 코드가 이 이점을 무시할 만큼 효율적일까?
정담은 yes다.
이진 탐색 코드가 if문도 많고 첫 번째 풀이법에 비해 코드량이 상당히 길지만 시간 복잡도가 주는 효율성이 이 모든 것을 제친다.
즉, 코드가 간결하다고 해서 좋은 것이 아닌 것!
2. Successful Pairs of Spells and Potions (No.2300)
문제 설명
You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.
You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.
Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.
해석
n과 m 사이즈를 가진 두 양수의 배열을 가진 spells와 potions가 주어지고 각 각의 요소들은 spell이 가진 힘과 potion이 가진 영향력을 가리킨다고 합니다.
만약 성공 조건이 정수로 주어지고, spell과 potion의 곱으로 성공 여부를 파악할 수 있다고 했을 때, 각 각의 spell이 성공할 수 있는 potion과의 조합 수를 차례대로 담은 배열을 반환하는 함수를 구현해주세요.
예제
코드
//이중 for문을 사용한 풀이 법
function successfulPairs(spells: number[], potions: number[], success: number): number[] {
const answer = [];
potions.sort((a,b) => a-b)
for (let i = 0 ; i < spells.length ; i++){
let successful = 0;
for (let j = 0 ; j < potions.length ; j++){
if(spells[i]*potions[j] >= success) {
successful = potions.length - j
break;
}
}
answer.push(successful)
}
return answer
};
//이진 탐색을 이용한 해결 책
function successfulPairs(spells: number[], potions: number[], success: number): number[] {
const answer = [];
potions.sort((a,b) => a-b)
for (let i = 0 ; i < spells.length ; i++){
const leastPotionStrength = Math.ceil(success/spells[i]);
const successful = potions.length - findIndex(potions,leastPotionStrength)
answer.push(successful)
}
return answer
};
function findIndex(potions : number[], target: number) :number {
let left : number = 0;
let right : number = potions.length - 1;
let mid : number;
while (left <= right) {
mid = Math.floor((left + right) / 2);
if (potions[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}🗒️코멘트
우선, 처음 문제를 받았을 때, 가장 먼저 든 생각은 역시 이중 for 문이었다.
단순하게 두개의 배열 내부에 있는 요소의 합이 성공 조건보다 크거나 같을 경우의 세를 세어주었고 그 수를 배열안에 push로 담아냈다.
물론 성공은 했지만 역시나 이런 문제가 Medium 레벨인데에는 효율성을 강조하기 때문이다.
시간 복잡도를 조금이라도 줄이기 위해서 다음과 같이 생각했다.
-
포션의 영향력을 오름차순으로 정렬해서 spell과 조합시 성공 조건을 만족할 수 있는 최소의 영향력을 찾기 위해 오름차순 정리
-
최소의 영향력의 인덱스 값을 찾기 위해 이진 탐색 적용
-
이진 탐색 위치를 기점으로 찾은 갯수를 배열에 담아 반환
깔끔하게 첫 번째 풀이 보다 약 3배 정도 빠르다는 결론이 나오고 성공!
3. Boats to Save People (No.0881)
문제 설명
You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person.
해석
각 사람의 몸무게가 적힌 배열이 주어지고 2명 밖에 탑승할 수 없는 보트의 무게 한도가 주어졌을 때, 모든 사람을 태우기 위해서는 몇 개의 보트가 필요한지 최소값을 반환하는 함수를 구현해주세요.
예제
코드
function numRescueBoats(people: number[], limit: number): number {
let peopleSorted = people.sort((a, b) => a - b)
let left = 0
let right = people.length-1
while(left < right) {
if(peopleSorted[left] + peopleSorted[right] <= limit) left += 1
right -= 1
}
return people.length - left
};🗒️코멘트
NULL
