Algorithm문제풀이: LeetCode의 #278 First Bad Version (easy)
// 문제링크: https://leetcode.com/problems/first-bad-version/
// 사용언어: 자바스크립트
// 로직:
// 포인터 세가지를 사용하고 ( left, right, pivot), while을 사용하여 안에 if 조건을 넣음으로써, 현재 가리키고있는 integer가 true인지, 그리고 바로 이전 integer는 false인지 확인하기
// pivot은 받아오는 integer의 값의 절반이 되도록 만들고,
// pivot이 가리키는 integer가 'true'이면서 동시에 pivot-1이 가리키는 integer는 'false'라면, 우리가 찾는 first bad version이므로 pivot을 리턴한다.
// pivot은 if 조건문을 통해 값이 'false' 일 경우에는 'left'를 pivot+1으로 reassign 하며,
// pivot은 if 조건문을 통해 값이 'true' 일 경우에는 'right'를 pivot-1으로 reassign 한다.
// 성능: Big O notation as O(log n), Runtime: 60 ms & Memory Usage: 41.8 MB
// 솔루션:
var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let left = 1;
let right = n;
// while loop with ‘left’ being less than or equal to ‘right’
while (left <= right) {
let pivot = Math.floor((left + right) / 2);
// if isBadVersion(i) outputs true, than return pivot
if (isBadVersion(pivot) == true && isBadVersion(pivot-1) == false) {
return pivot;
}
if (isBadVersion(pivot) == false) left = pivot + 1;
if (isBadVersion(pivot) == true ) right = pivot - 1;
}
};
};
위 내용은 문제를 푸는 수 많은 방법중에 하나입니다. 여러분의 솔루션 또는 의견을 댓글로 공유해주세요!
