[Leetcode] 34. Find First and Last Position of Element in Sorted Array

April Leetcode Challenge 2021에서 4월 29일에 (PST) 출시된 문제를 풀어보도록 하겠다.

 

문제는 아래 링크를 참고하길 바란다.

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

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

항상 말씀드리지만, 코딩인터뷰에서는 우선 문제를 읽고 이해를 한 다음에 인터뷰어에게 설명하는 과정이 필요하다.

미국 회사 기준입니다. 한국도 그런진 모르겠습니다. 제가 입사할때는 코딩테스트라는게 없던 시절이라...ㅠㅠ
혹시 구글코리아, 아마존코리아, 페이스북코리아 같이 미국에 본사가 있는 회사에 지원하실때에는 제가 소개시켜드리는 방식으로 코딩테스트를 진행하셔야 합니다.

 

주어진 정수형 배열 nums 가 오름차순으로 정렬되어 있으니, 주어진 목표값의 시작지점과 종료지점을 찾아라는 문제이다. 만약 배열에 목표값이 없으면, {-1, -1} 을 리턴하라고 되어있다. 문제를 읽다보니 배열이 정렬되어 있다는 게 눈에 딱 띈다. 이건 BinarySearch (이진탐색) 써야하는거다라고, 근데 시작인덱스와 종료인덱스를 찾으라고? 조금 변형시켜서 검색하면 되겠다. 라는 생각을 했다.

역시나 Follow-up 이 붙어있었는데, 이진탐색의 시간복잡도가 log n 이니까 이진탐색이 맞구나!

Follow-up: Could you write an algorithm with O(log n) runtime complexity?

 

우선 문제를 좀 더 명확히 하기 위해서 몇가지 질문이 필요하다.

• 주어진 배열은 중복값이 들어갈 수 있는지? 모든 배열이 1가지 값으로 셋팅될 수도 있는지?
• 배열의 사이즈는 어떻게 되는지? 만약 null 이거나 크기가 0인 경우에는 어떤 값을 리턴해야 하는건지?
• 배열의 원소값과 목표값의 범위는 각각 어떻게 되는지?
  (Integer.MIN_VALUE ~ Integer.MAX_VALUE 라면 MIN/MAX 일때 ±1 의 오버플로우를 조심)

위 질문은 문제에 나와있기 때문에 불필요하다고 느껴질 수 있지만, 인터뷰 상황에서 모든 조건이 Leetcode와 동일하지 않을 가능성이 높아서 연습하는 과정이 필요합니다. 그냥 A를 구현해봐 라고 말로 하는 경우도 있습니다. 그럼 문제를 복붙해줄 수 있냐고 물어야 하고, 문제를 보고는 A를 구현하라고 하는게 맞냐? 고 묻고, 예제 Input/Output 을 물어보면서 명확히 해나가야하는 경우가 있습니다. 티키타카가 필요한데 미국회사에서는 이 과정을 매우 중요하게 생각합니다. 당연히 class Solution { ~ } 이런 부분도 안주어지기 때문에 요구사항에 따른 자료구조 및 메소드 설계 능력도 봅니다. 이 부분은 정답이 있는 부분이 아니라 자신의 지식과 코딩스킬 및 스타일을 인터뷰어에게 보여주는 것이라 생각하는 대로 진행하시면 됩니다. 그러니 준비를 하시는 분이라면 미리 준비를 해둬야겠죠 :)

 

어느정도 문제가 명확화되고 풀 수 있겠다는 생각이 들면, 본인이 생각한 풀이법을 인터뷰어에게 얘기를 해준다.

이 문제를 보니까 (오름차순으로) 정렬되어 있는 정수형 배열이고, 목표값을 찾는 것이니까 이진탐색을 이용하면 될 것 같습니다. 근데 배열에서의 목표 (target) 값의 범위를 찾는게 이 문제의 목표 (Goal) 이니까, 흔히 사용하는 이진탐색에서 변형 (variation) 이 필요할 것 같습니다. 내가 생각하기에 이진탐색의 조건 3부분에서 mid가 target과 동일할 때 mid의 좌우를 살펴서 target 의 존재유무에 따라서 low/mid/high 값을 변경해주면 될 것 같습니다. 그렇게 2번의 이진탐색을 거치면 시작지점과 종료지점을 찾을 수 있다고 생각합니다.

 

이렇게 얘기하면 인터뷰어가 반응을 할 것이다.

좋아요. 구현해보세요.

3조건은 어떤 조건에 의해 분기되는 것이죠?

mid의 좌우를 살핀다는 부분이 좀 불명확한데, 구체적으로 얘기해줄 수 있겠어요?

 

이런식으로 본인의 풀이법에 대해 질문 (tackle) 이 들어올 수 있으나 긴장하지 말고 이 모든 것이 실제 일하는 과정과 비슷하니, 생각하면서 진행하면 좋을 것 같다. (물론 저에게 하는 말입니다.)

위 설명의 디테일이 매우 부족하기 때문에 어차피 질문 들어올 것이지만, 아래에서 풀이법을 설명할 예정이니 문답은 생략하고 풀이를 보겠다.

현재 인터뷰이의 입장인데, 인터뷰어를 예상하는 것도 웃기고요...ㅠㅠ 출제자의 의도.......

 

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = binarySearch(nums, target, true); // 시작지점을 먼저 찾음
        if (start == -1) { // 배열 내에서 못 찾은 경우에는 [-1, -1] 리턴
            return new int[] {-1, -1};
        }
        
        int end = binarySearch(nums, target, false); // 종료지점을 찾아서
        return new int[] {start, end}; // 결과 배열로 리턴
    }
    
    private int binarySearch(int[] nums, int target, boolean isStart) {
        int low = 0; // 이진탐색의 시작
        int high = nums.length - 1; // 이진탐색의 종료
        while (low <= high) { // 끝이 -1 이었기 때문에 <= 로 비교
            int mid = low + (high - low) / 2; // int 오버플로우 방지
            if (nums[mid] > target) { // nums[mid]가 목표값보다 큰 경우
                high = mid - 1; // mid 미만지점에 존재할 것이므로
            } else if (nums[mid] < target) { // nums[mid]가 목표값보다 작은 경우
                low = mid + 1; // mid 초과지점에 존재할 것이므로
            } else { // nums[mid]가 목표값인 경우
                if (isStart) { // 만약 시작지점을 찾는 경우라면
                    // mid가 이진탐색의 시작과 같은 경우이거나 nums[mid]의 한 칸 왼쪽이 목표값이 아닌 경우는
                    // mid가 목표값의 시작지점이라고 할 수 있음
                    if (mid == low || nums[mid - 1] != target) { 
                        return mid;
                    }
                    // mid가 이진탐색의 시작이 아니고, nums[mid - 1]에 목표값이 있는 경우는
                    // 현재보다 왼쪽에 목표값이 더 존재한다는 말이므로 이진탐색의 종료지점을 mid - 1로 옮겨서 재탐색
                    high = mid - 1; 
                } else { // 종료지점을 찾는 경우라면
                    // mid가 이진탐색의 종료와 같은 경우이거나 nums[mid]의 한 칸 오른쪽이 목표값이 아닌 경우는
                    // mid가 목표값의 종료지점이라고 할 수 있음
                    if (mid == high || nums[mid + 1] != target) { 
                        return mid;
                    }
                    // mid가 이진탐색의 종료가 아니고, nums[mid + 1]에 목표값이 있는 경우는
                    // 현재보다 오른쪽에 목표값이 더 존재한다는 말이므로 이진탐색의 시작지점을 mid + 1로 옮겨서 재탐색
                    low = mid + 1;
                }
            }
        }
        // 이진탐색을 끝냈지만, 아무것도 발견하지 못했다는 것은 주어진 배열에 목표값이 없다는 뜻
        return -1;
    }
}

이진탐색에서 가장 중요한 것은 mid 값의 설정과 비교조건 설정이라고 생각한다. 해당 문제는 이진탐색의 기본에 충실하면 되고, 탐색 후에 mid 위치가 정말 시작/종료지점인지에 대해서 확인하는 작업만 거치면 되는 것이다.

이진탐색의 기본적인 것은 다른 분들의 블로그나 leetcode.com/explore/learn/card/binary-search/ 에 잘 설명되어 있으니 참고하시면 좋을 것 같다.

 

두 번의 이진탐색이 필요하니 boolean 값을 통해 분기를 해준다. 그리고 배열의 mid 위치에 목표값을 찾았을때 시작지점을 찾는 경우에는 왼쪽을 확인해보면 되고, 종료지점을 찾는 경우에는 오른쪽을 확인해보면 된다. 확인해서 만약 있는 경우에는 이진탐색의 범위를 줄여서 재탐색할 수 있게 해준다. 어차피 메소드 전체 도는데 $O(log n)$의 비용만 발생한다. 매우 효율적인 알고리즘이라고 생각한다.

 

결국 시간복잡도는 이진탐색이므로 $O(log n)$이 되고, 공간복잡도는 거의 선언된 변수들이 없기 때문에 상수시간인 $O(1)$이 된다.

 

시작을 찾는 메소드, 종료를 찾는 메소드 2개를 선언하는 것도 상관없을 것 같다. 어쨌든 시간/공간복잡도에는 크게 영향을 미치지 못하니까.

 

마지막으로 코딩을 완료 한 뒤에 손으로 디버깅하면서 인터뷰어에게 설명하는 작업을 꼭 거쳐야 함을 잊으면 안된다.