-
leetcode top interview 150 | Find Peak Element | Binary SearchPS 2023. 9. 5. 09:45
Question
양 옆의 수보다 큰 경우를 peak이라 한다. 주어진 정수배열에서 peak을 찾고 해당 인덱스를 반환하라.
만약 여러개의 peak이 존재하면 어떤 인덱스를 반환해도 된다. 배열 밖의 요소들은 가장 작은 수로 인지해라.
알고리즘의 시간복잡도는 O(logN)으로 작성해라.
Accepted Code
class Solution { public int findPeakElement(int[] nums) { int start = 0; int end = nums.length - 1; while(start<end){ int mid = (start + end) / 2; if(nums[mid] < nums[mid+1]){ start = mid + 1; }else{ end = mid; } } return end; } }
Solve
일반적인 for문이면 시간복잡도가 O(n)이기 때문에 큰 데이터 집합에서 O(logN)으로 빠른 검색이 가능한 이진탐색 알고리즘을 활용했다.
Binary Search(이진 탐색) :
선형구조에서 중간 요소를 선택하고 찾으려는 값과 비교하여 원하는 요소를 효율적으로 찾는 검색 알고리즘으로, 검색 범위를 반으로 줄여가며 탐색하기 때문에 평균 O(logN)가 소요된다.기존의 이진탐색은 원하는 값을 찾기 위해 정렬된 배열 혹은 리스트에서 중간값을 정하고 찾아가지만, 해당 문제는 양 옆보다 크면 peak이라는 조건이 있기 때문에 정렬을 하지 않고 옆의 인덱스만 비교하는걸로도 확인이 가능하다.
따라서 start인덱스를 0으로 end인덱스를 nums배열의 끝으로 초기화하고, 중간 인덱스보다 다음 요소가 크면 nums[mid]는 peak 값이 될 수 없기 때문에 start 지점을 mid + 1로 갱신해서(반절로 줄이면서) 탐색을 계속한다.
다시 탐색한 중간 인덱스가 다음 요소 보다 큰 경우면 peak 값이 될 수 있다. 따라서 end 인덱스에 해당 위치를 저장해주고 더 작은 인덱스와 비교하기 위해 왼쪽으로 이동해서 다시 탐색을 진행한다.
'PS' 카테고리의 다른 글
leetcode top interview 150 | Kth Largest Element in an Array | PriorityQueue (0) 2023.09.12 leetcode top interview 150 | Binary Tree Right Side View | DFS (0) 2023.09.06 leetcode top interview 150 | Min Stack | ArrayList (0) 2023.09.01 leetcode top interview 150 | Valid Anagram | HashMap (0) 2023.09.01 leetcode top interview 150 | Ransom Note | HashMap (0) 2023.09.01