[LeetCode] 162. Find Peak Element

https://leetcode.com/problems/find-peak-element/

Find Peak Element - LeetCode

Find Peak Element.

말 그대로 int 배열 중 피크점의 index를 찾아주면 된다.

peak는 여러개 있을 수 있는데 아무거나 찾아주면 된다.

간단하게는 왼쪽 오른쪽보다 높은 값의 index를 return하면 된다.

 

그렇다면 왼쪽이 없는 첫번째와 오른쪽이 없는 마지막은?

-1과 마지막다음 index의 배열 값은 -inf 로 설정한다.

즉, 첫 값은 무조건 왼쪽보다 높고, 마지막 값은 무조건 오른쪽보다 높다는 말.

 

문제는 아주 간단하다.

딱 보면 슥 배열을 훑어가면서 왼쪽 오른쪽보다 크면 바로 return을 해주면 되기 때문.

 

하지만 문제는 설명의 마지막부분에 있다.

You must write an algorithm that runs in O(log n) time.

시간복잡도가 O(log n)이어야 한다는 말이다.

앞서 말한 방법은 앞에서 부터 모든 배열을 살펴야하므로 시간복잡도는 O(n)이 된다.

분명 시간초과가 날것...이라 생각하면서도 그냥 돌려봤더니 웬걸? 된다.

LeetCode는 좀 관대한 것인지...

그래도 정석적인 방법을 써보려 한다.

 

내가 O(log n)을 보자마자 떠오른 것은 Binary Search (이진 탐색) 다.

어떠한 배열에서 적절한 값을 찾고자 할때 많이 사용하는데,

방법은 간단하다!

up/down 게임을 해본적이 있을 것이다.

1~100에서 골라야한다면 우리는 보통 중간값인 50을 먼저 외친다.

그리고 up이 나온다면 50~100의 중간인 75, 또 up일 경우엔 75~100 사이인 87(또는 88)... 이런식으로 값을 찾아가는 것이다.

 

필요한 변수는 무엇일까?

up/down 게임에서도 보듯, 시작점인 1과 끝점인 100, 그리고 우리가 외칠 중간값인 50이다.

시작은 index의 시작인 0으로, 마지막은 배열의 길이-1로 설정한다.

중간값은 산술평균해준다.

int start = 0;
int end = nums.size()-1;
int mid = (int)(start+end)/2;

이제 우리는 딱 이 세 수만 비교하며 찾아갈 것이다.

peak를 찾으려면 커지는 방향으로 따라가야할까 작아지는 방향으로 따라가야할까?

peak는 봉우리이므로 산을 오르듯 커지는 방향으로 따라가야한다.

그렇다면 세 수를 비교하며 peak를 찾아 따라가보자.

비교할 경우는 다음과 같다.

 

nums[start] 와 nums[mid]
nums[end] 와 nums[mid]
nums[start] 와 nums[end]

 

1. nums[start] 와 nums[mid]

 

1-1. 만약 시작점이 중간점보다 크다면 어떻게 될까?

우리는 커지는 방향으로 따라가면 되므로, peak는 시작점과 중간점 사이 어딘가에 있다는 말이다.

1~100 에서 50을 불렀더니 down 이라고 하는 상황과 같다.

그럼 우리는 범위를 1~50으로 줄이게 된다. 50부터 100은? 더이상 상관없다.

peak는 한개만 찾으면 되므로.

 

up/down 에서는 시작점이 1, 끝점이 100, 중간점이 50이었는데 이것이 시작점이 1, 끝점이 50으로 변했다.

mid 는 처음처럼 중간값으로 잡으면 된다.

코드도 이렇게 짜보자.

if (nums[start]>nums[mid]) end = mid;
mid = (int)(start+end)/2;

1-2. 그럼 만약 시작점이 중간점보다 작다면?

아직은 알 수 없다. 이 경우에는 끝점을 비교해주면 된다.

 

2. nums[end]와 nums[mid]

2-1. 끝점이 중간점보다 크다면?

1-1과 같은 상황이지만 변수만 반대로 바꿔주면 된다.

if (nums[end]>nums[mid]) start = mid;
mid = (int)(start+end)/2;

2-2. 끝점이 중간점보다 작다면?

역시 아직은 알 수 없다.

 

3. nums[start]와 nums[end]

이 둘을 비교하는 것은 사실상 의미가 없다.

 

그렇다면 우리에겐 아직

1-2와 2-2가 풀리지 않았는데, 이 경우엔 어떻게 해야할까?

 

최초에 우린 커지는 방향으로 움직이기로 했다.

그렇다면 결국 중간점의 양쪽을 봐줘야한다는 말이다.

 

4. nums[mid]와 nums[mid+1]

중간값보다 그 오른쪽값이 크다면 우리는 바로 오른쪽으로 움직여주면 된다.

if (nums[mid+1]>nums[mid]) start = mid;
mid = (int)(start+end)/2;

그렇지 않고 중간값의 왼쪽값이 중간값보다 크다면 왼쪽으로 움직여주면 된다.

하지만 둘다 중간값보다 크지 않다면?

애초에 우린 이런값을 찾으려 했다. 이때는 mid가 peak가 된다.

하지만 이렇게 분기점을 여러번 나눌 필요가 없다.

어차피 우리는 오른쪽아니면 왼쪽으로 움직일 것이기 때문에

더이상 오른쪽으로 움직일 일이 없고, 더 봐줄 조건도 없으므로 위의 코드부분이 아니라면 중간이 peak일 경우 손해는 조금 있겠지만 무조건 왼쪽으로 움직여줘도 된다.

 

if (nums[mid+1]>nums[mid]) start = mid;
else end = mid;
mid = (int)(start+end)/2;

 

자 이제 움직이는 과정은 끝난다.

근데 이걸 몇번 반복해야 할까??

극단의 케이스를 생각해보자.

 

많이 줄여서 0,1 중에서 고른다고 생각해보자.

(start = 0, mid = 0, end = 1)

start와 mid가 겹치게 되었고,

우리는 end가 peak라고 알 수 있다.

 

1,0 중에 고른다고 생각해보자.

(start = 1, mid = 1, end = 0)

역시 start와 mid가 겹치게 되었고,

이때는 start가 peak라는 걸 알 수 있다.

 

즉, start가 mid와 같아질때까지 위 코드들을 돌리고,

그 때의 결과 값으로는 start값과 end값 중 큰 값을 내뱉으면 된다.

 

전체 코드는 아래와 같다.

오른쪽으로 이동하는 경우와 왼쪽으로 이동하는 경우 뿐이므로 둘을 합쳤다.

 

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int start = 0;
        int end = nums.size()-1;
        int mid = (int)(start+end)/2;
        while (start<mid) {
            if (nums[start]>nums[mid] || nums[mid]>nums[mid+1]) end = mid;
            else start = mid;
            mid = int(start+end)/2;
        }
        return nums[start]>nums[end]?start:end;
    }
};