Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
Tags
- 카카오프로젝트100
- python
- 보안뉴스 요약
- javascript
- 파이썬
- 자바스크립트 기본 문법
- 자바스크립트 prototype
- 자바스크립트 node
- php
- 보안뉴스한줄요약
- 자바스크립트 객체
- 자바스크립트 element api
- 다크웹
- ES6
- 보안뉴스요약
- 자바스크립트 API
- 보안뉴스
- 깃허브
- Oracle SQL
- 카카오프로젝트
- 오라클
- GIT
- 랜섬웨어
- 자바스크립트
- 카카오프로젝트 100
- oracle db
- oracle
- 자바스크립트 jQuery
- numpy
- 보안뉴스 한줄요약
Archives
- Today
- Total
FU11M00N
[LeetCode] Merge Sorted Array - Javascript 본문
Find Peak Element
[양옆의 요소와 비교해 큰 수 인지 확인]
제약 조건
1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
nums[i] != nums[i + 1] for all valid i.
Example
ex1) Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
ex2) Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
문제 접근 방식
문제 설명에 Y"ou may imagine that nums[-1] = nums[n] = -∞"라는 설명이 있다.
즉 nums 배열의 -1 인덱스와 n 인덱스는 가장 최솟값을 가진다고 되어 있다는 의미이다.
이 점을 생각해 해당 문제를 이진 탐색으로 풀 수 있다.
맨 처음 while 반복문으로 start가 end보다 커질 때 까지 반복한다.
mid는 배열의 중간의 값으로 초기화 되도록
mid = Math.floor((start + end) / 2); 연산을 수행한다.
그 후 mid의 이전 인덱스와 이후 인덱스를 비교해 mid가 양옆 요소보다 큰지 확인하고 크다면 해당 인덱스를 리턴한다.
만약 아니라면 mid의 요소 값이 left 보다 크다면 end를 mid-1로 값을 업데이트하고, 작다면 start를 mid+1 값으로
업데이트를 하여 절반을 날려버린다.
이런 방식으로 접근하면 왼쪽이나 오른쪽의 절반 중 한쪽에 요소가 양옆보다 큰 수가 없어 다른 한쪽을 버려버리면 안 될 것 같지만,
이렇게 해도 되는 이유는 nums[-1]과 nums[n] 인덱스는 -Infinity 값을 가지기 때문에 배열의 맨 끝까지 가게 되면 어차피 최솟값과 요소의 값을 비교하기에 무조건 양옆보다 큰 요소가 나온다.
solve 전체 코드
/**
* @param {number[]} nums
* @return {number}
*/
var findPeakElement = function(nums) {
let start = 0, end = nums.length - 1
let mid = 0;
while (start <= end) {
mid = Math.floor((start + end) / 2);
const val = nums[mid];
const left = nums[mid - 1] || -Infinity
const right = nums[mid + 1] || -Infinity
if (val > left && val > right) return mid;
if (left > val) {
end = mid - 1
} else {
start = mid + 1
}
}
return 0;
};
'알고리즘' 카테고리의 다른 글
[LeetCode] Find Minimum in Rotated Sorted Array - Javascript (0) | 2023.09.04 |
---|---|
[LeetCode] Search in Rotated Sorted Array - Javascript (0) | 2023.09.04 |
Linear Probing 방식 Hash Table을 구현 - javascript (0) | 2023.09.04 |
[LeetCode] Sort List - Javascript (0) | 2023.09.04 |
[LeetCode] Contains Duplicate II - Javascript (0) | 2023.09.01 |
Comments