LeetCode: 34번 (Find First and Last Position of Element in Sorted Array) [JAVA]

문제 링크

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Find First and Last Position of Element in Sorted Array - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 이진탐색을 베이스로 배열 속 특정 위치를 찾는 함수를 작성
   1) 특정 한 위치까지 근접했을 때 해당 값보다 target이 더 크면 중간값+1을, target이 더 작으면 중간값을 반환
2. 주어진 nums 배열이 없다면 {-1, -1}을 반환
3. 주어진 target에서 0.5를 빼고 더해 floor와 ceiling 변수 초기화 후, 이를 가지고 앞선 함수를 통해 target의 경계 위치를 반환
4. 만약 해당 구간의 시작과 끝이 역전되었다면 target 값이 없는 경우기 때문에 {-1, -1}을, 그 외에는 구간의 시작값과 마지막값을 반환

 문제에서 주어진 nums 배열에는 정렬은 되어 있지만 여러 값들이 중복되어 들어가있고, 같이 주어진 taget 값에 대해 해당 값들이 존재하는 구간(혹은 {-1, -1})을 반환해야 하는 문제이다. 만약 단순히 이진탐색을 활용해 target을 찾는 경우 target 구간 속 임의의 값에만 접근을 하기 때문에 구간 탐색을 위해 추가적인 탐색을 해야 해 로직이 복잡해진다.
 이를 위해 고민하다가 이 다음 문제인 Search Insert Position을 해결하면서 해결방법을 찾을 수 있었다. 앞선 문제의 경우 배열 속 없는 값에 대해 해당 배열 속 적절한 위치를 반환하는 문제였는데, 이를 이번 문제에 적용해 구간을 쉽게 찾을 수 있다. 주어진 target 값에서 기존 배열에 없는 값을 만들기 위해 0.5라는 값을 빼고 더해 floor와 ceiling이라는 변수를 초기화하고, 이를 nums 배열 속 적절한 위치(해당 변수가 들어갈만한 위치)를 반환받는 방법이다. 이를 통해 각각 floor와 ceiling이 들어갈만한 위치는 곧 target에 근접한 위치기 때문에 이들을 통해 구간을 쉽게 얻을 수 있다.
 우선 이진탐색을 기반으로 특정 인덱스를 반환하는 함수를 작성한다. 큰 흐름에서는 같으나 결국 확실한 값이 배열 속에는 없기 때문에 탐색을 하게 되는 start와 end가 동일할 때는 특정 위치를 반환하도록하고, 그 외에 start > end가 되는 상황에 대한 처리를 해준다. 그렇게 해당 함수를 통해 앞선 floor와 ceiling이 들어갈만한 위치를 반환받고, 그 다음에 두 변수에 대한 비교를 통해 적절한 값을 반환해준다. 만약 구간의 시작보다 끝이 앞이라면 이는 target이 없기 때문에 {-1, -1}을 반환하고, 그 외의 경우엔 시작과 끝 값을 넣어 답을 반환한다.

 

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {//배열이 없는 경우
            return new int[]{-1, -1};
        }

        double floor = target - 0.5, ceiling = target + 0.5;
        int floorIndex, ceilingIndex;

        floorIndex = binarySearch(nums, floor, 0, nums.length - 1);
        ceilingIndex = binarySearch(nums, ceiling, 0, nums.length - 1) - 1;

        if (floorIndex > ceilingIndex) {//범위 시작과 끝이 역전된 경우 -> target값이 없음
            return new int[]{-1, -1};
        }

        return new int[]{floorIndex, ceilingIndex};
    }

    int binarySearch(int[] nums, double target, int start, int end) {
        if (start > end) {
            return start;
        }

        int mid = (start + end) / 2;

        if ((double) nums[mid] < target) {//중간값보다 target이 크다면
            if (start == end) {//한 개인 경우
                return mid + 1;
            }

            return binarySearch(nums, target, mid + 1, end);
        } else {//nums[mid] >= target
            if (start == end) {//한 개인 경우
                return mid;
            }

            return binarySearch(nums, target, start, mid - 1);
        }
    }
}

결과