[LeetCode] 1095. Find in Mountain Array

https://leetcode.com/problems/find-in-mountain-array/

Find in Mountain Array - LeetCode

문제 유형 : 이진 탐색

문제 난이도 : Hard

 

문제

(This problem is an interactive problem.)

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index does not exist, return -1.

You cannot access the mountain array directly. You may only access the array using a MountainArray interface:

• MountainArray.get(k) returns the element of the array at index k (0-indexed).
• MountainArray.length() returns the length of the array.

Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

 

산 모양의 배열이 있다. 

산 모양의 배열에 있는 target 값의 가장 작은 인덱스를 구하시오. 없으면 -1을 반환하시오.

당신은 산 모양의 배열에 직접적으로 접근할 수 없다. 대신, 두 메서드로 값을 불러올 수 있다.

MountainArray.get(k) 는 배열 k번째 인덱스의 값을 반환한다.(0-indexed 기준)

MountainArray.length()는 배열의 길이를 반환한다.

 

MountainArray.get(k)의 호출 횟수가 100이 넘어가면 영어로 자격 박탈 메시지가 나온다.

(101번 이상 호출은 안된다.)

 

풀이

이진 탐색을 3번 하여 찾을 수 있다.

우선, 산 배열의 봉우리를 구한다.

이진 탐색을 이용하는데, 만약 오른쪽 요소가 더 크면, 더 오른쪽으로 가야 하므로 left를 peak+1로 업데이트하여 반복한다.

아니라면, right을 peak로 업데이트하여 반복한다.

이걸 left < right동안 반복하면 된다.

그러면, peak에는 최고 높이의 인덱스가 위치하게 된다.

 

이제 오르막길부터 이진탐색을 한다. 더 작은 인덱스를 반환해야 하기 때문이다.

left는 0, right는 peak로 초기화한다.

여기부터는 일반적인 이진탐색을 해주면 된다.

값을 찾으면, 그 인덱스를 반환하면 된다.

 

그러고 찾지 못하면, 내리막길 이진탐색을 한다.

left는 peak+1, right는 MountainArray.length()-1로 초기화한다.

탐색 중 값을 찾으면, 그 인덱스를 반환하면 된다.

 

양 쪽을 다 탐색했는데도 찾지 못하면, -1을 반환한다.

 

 

코드

C++

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        
        int left = 0;
        int right = mountainArr.length() - 1;
        int peak;

        // Peak 찾기
        while (right > left) {
            peak = (left + right) / 2;
            int peakVal = mountainArr.get(peak);
            int rightVal = mountainArr.get(peak+1);

            if (peakVal > rightVal) {
                right = peak;
            } else {
                left = peak + 1;
            }
        }

        left = 0;
        right = peak;

        while (right >= left) {
            int mid = (left + right) / 2;
            int midVal = mountainArr.get(mid);
            if (midVal == target)
                return mid;
            if (midVal < target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        left = peak + 1;
        right = mountainArr.length() - 1;
        while (right >= left) {
            int mid = (left + right) / 2;
            int midVal = mountainArr.get(mid);
            if (midVal == target)
                return mid;
            if (midVal > target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        return -1;
    }
};