[LeetCode] 21 - Merge Two Sorted Lists

문제

• 링크: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array
• 난이도: Medium
• 태그: 배열, 이진 탐색
• 결과: Time: 0 ms (100%), Space: 14.06 MB (78.96%)

풀이

class Solution {
public:
    int findMin(vector<int>& nums) {
        return solve(nums, 0, nums.size() - 1);
    }

    int solve(vector<int>& num, int start, int end)
    {
        if (end - start < 2)
        {
            return min(num[start], num[end]);
        }

        // 중간 인덱스 계산
        int mid = (start + end) / 2;

        // 오름차순 정렬이 깨지기 시작한 부분 -> 최솟값 발견
        if  (num[mid] < num[mid - 1])
        {
            return num[mid];
        }

        // 왼쪽 영역이 정렬되어 있는 경우
        if (num[start] <= num[mid])
        {
            // 그리고 오른쪽 영역까지도 정렬된 경우
            if (num[mid] <= num[end])
            {
                // 가장 왼쪽에 있는 값이 최솟값
                return num[start];
            }

            // 왼쪽 영역만 정렬된 경우
            // 오른쪽 영역에서 정렬이 깨지는 부분 찾으러 가기
            return solve(num, mid + 1, end);
        }

        // 오른쪽 영역이 정렬된 경우
        // 왼쪽 영역에서 정렬이 깨지는 부분 찾으러 가기
        return solve(num, start, mid - 1);
    }
};

회전된 배열에서의 이진 탐색은 고전적인 알고리즘 문제다. 약간 변형해서 최솟값을 찾으라는 문제였는데, 회전하기 전 배열은 오름차순 정렬된 상태이므로 이 정렬이 깨진 부분을 찾아내면 된다.

배운 점과 후기

회전된 배열에서의 이진 탐색을 직접 짜야하는 문제였다. 중간 인덱스 계산하고 재귀 들어가는 것 자체는 쉬운데, 조건을 놓치는 것에 주의해야겠다.

이 포스트는 달레 스터디(4주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.