리트코드 - 162. Find Peak Element

리트코드 - 162. Find Peak Element

출처 - https://leetcode.com/problems/find-peak-element/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

피크 요소는 주변 요소보다 엄격하게 큰 요소를 의미합니다.

0-인덱스 정수 배열 nums가 주어지면, 피크 요소를 찾아서 해당 인덱스를 반환해야 합니다. 배열에 여러 개의 피크가 있을 경우, 그 중 하나의 피크의 인덱스를 반환하면 됩니다.

여기서 nums[-1] = nums[n] = -∞라고 가정합니다. 다시 말해, 배열 바깥에 있는 이웃 요소보다 요소는 항상 엄격하게 크다고 간주됩니다.

O(log n) 시간 내에 실행되는 알고리즘을 작성해야 합니다.

 

의사코드

왼쪽 포인터 = 0 오른쪽 포인터 = 배열길이 - 1 반복문 시작(왼쪽 포인터 < 오른쪽 포인터)     중간 값 = 왼쪽 + 오른쪽 / 2     if (nums 배열 mid 인덱스 값 < 다음 배열 값)         left = mid + 1     else         right = mid 반복문 종료 left 리턴

 

풀이코드

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int mid = (left + right) / 2;

            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

코드설명

이진탐색을 이용한 풀이이다.

left 포인터와 right 포인터를 만들어서 처음과 끝을 설정해놓고, 중간값을 찾는다.

 

이 중간값을 인덱스로 가지는 배열과 배열의 다음값을 비교해보고 다음값이 크다면 오른쪽 배열을 탐색하기 위해 left에 mid +1 을 한다.

반대로 다음값이 작다면(문제에서 인접하는 배열값은 같지 않다는 조건이 있다.) 왼쪽 배열을 탐색하기 위해 right을 mid로 한다.

이렇게 이진탐색을 하여 조회를 하면 최종적으로는 left와 right가 같아지는데, 이 때의 left 값을 리턴하면 피크요소가 된다.

 

예를 들어 {1,2} 배열이 있고, {2,1} 배열이 있다고 하자.

 

left는 0이고, right은 1이 될 것이다.

mid를 계산하면 (0+1)/2 = 0 이 될 것이고 0번째 인덱스와 1번째 인덱스를 비교한다.

 

첫번째 사례의 경우 다음 배열요소가 크므로(1 < 2) left를 mid+1인 1로 옮긴다. 이 때 left와 right이 같아지고, left값이 피크요소다.

두번째 사례는 다음 배열요소가 작으므로(2 > 1) right가 mid로 옮겨진다. 이 때도 마찬가지로 left와 right이 같아지고 left값이 피크요소가 된다.

 

위와 같은 사례를 볼 때 이진 탐색을 할 때 중간값을 찾고 left를 중간값 위치로 생각해버리면 루프에 빠지게 된다.

반드시 왼쪽을 추가할 때에는 다음값을 추가해줘야 해야한다.

 

시간복잡도 - O(log n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

처음에는 문제 하단 조건을 보지 못했었다.

인접한 배열요소는 같지 않다는 조건을 못봐서 코드가 지나칠정도로 복잡해졌었다.

O(log n) 시간 내에 끝내야 된다는 문장이 있어서 분명히 이진트리인데 어떻게 하라는건지 멘붕에 빠졌다가 조건을 확인하고 적어보니 그렇게 어렵진 않았다.

 

다른코드

class Solution {
    public int findPeakElement(int[] nums) {
        int start = 0;
        int end = n-1;

        while(start <= end) {
            int mid = start + (end - start)/2;
            if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) return mid;   // if mid == peak ( case 2 )
            else if(nums[mid] < nums[mid-1]) end = mid - 1; // downward slope and search space left side ( case 1)
            else if(nums[mid] < nums[mid+1]) start = mid + 1; // upward slope and search space right side ( case 3 )
        }
        return left;
    }
}

다른사람의 코드인데 위 코드를 돌려보니 인덱스 에러가 났다.

배열의 크기가 2일때 문제가 되는 것 같은데 이 때의 조건을 따로 추가해줘야 할 것 같다.

그렇지만 start와 end의 이동이 읽기 쉬운 코드같다.

 

성능상에 차이가 없다면 읽기 쉬운 코드가 유지보수에도 편하지 않을까 싶은 생각이다.

 

정리

이진탐색에서 정렬이 안되어 있어도 피크값을 찾을 수 있다.