[LeetCode] 81번 문제를 풀어보았다. (ft. java)

2022년 03월 28일 월요일 - 이거 이렇게 푼거 올려도 되나..?

오늘 올려볼 문제는 81번 Search in Rotated Sorted Array II 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

올릴까 말까 고민 마이 해따..

입력

사진에서도 볼 수 있듯이 int 배열 하나와 int 값 하나가 입력으로 들어온다.

---

풀이 및 코드

정렬된 배열을 어떠한 수만큼 돌린 배열이 주어질 때 target이 배열안에 있는지 판단하는 문제이다.

오늘은 처음부터 정답을 생각해냈다.

사실상 걍 for문 돌리면서 문제를 풀어도 풀리지 않을까 했는데 진짜 풀렸다...

이제 코드를 봐보자!

풀이코드

class Solution {
    public boolean search(int[] nums, int target) {
        for(int num : nums) if(num == target) return true; return false;
    }
}

정석적인 풀이는 아래와 같다.

풀이코드

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;

        while(left <= right)
        {
            mid = (left + right) / 2;

            if(nums[mid] == target) return true;

            if(nums[mid] < nums[left] || nums[mid] < nums[right])
            {
                if(nums[mid] < target && target <= nums[right])
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
            else if(nums[mid] > nums[left] || nums[mid] > nums[right])
            {
                if(nums[left] <= target && target < nums[mid])
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            else
            {
                right--;
            }
        }

        return false;
    }
}

---

제출 화면

사실 제대로 된 풀이로 문제를 푼게 아니라서 올리지말까하다가 풀긴 풀었으니 올린다...

내일은 제대로 된 풀이로 문제를 풀 수 있기를 바란다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.