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

2022년 03월 29일 화요일 - 오늘은 왜 이렇게 시간이 안가나요~~

오늘 올려볼 문제는 287번 Find the Duplicate Number 이라는 문제이다.

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

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

1분 컷이지만 follow up은 못 풀었다는 사실

입력

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

---

풀이 및 코드

길이가 n + 1인 배열에 1 ~ n까지의 원소가 있는데 이 때 딱 한 원소만이 중복된다고 할 때 이 중복된 원소를 찾아서 리턴하는 문제이다.

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

중복된 원소가 나왔는지 판단하는 boolean 배열을 만들고 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findDuplicate(int[] nums) {
        boolean[] count = new boolean[nums.length];

        for(int num : nums)
        {
            if(count[num])
                return num;
            else
                count[num] = true;
        }

        return 0;
    }
}

아래 코드는 공간복잡도 O(1)인 풀이이다.

풀이코드

class Solution {
    public int findDuplicate(int[] nums) {
        int fast = 0, slow = 0;
        fast = nums[nums[fast]];
        slow = nums[slow];

        while(nums[fast] != nums[slow])
        {
            fast = nums[nums[fast]];
            slow = nums[slow];
        }

        fast = 0;
        while(nums[fast] != nums[slow])
        {
            fast = nums[fast];
            slow = nums[slow];
        }

        return nums[fast];
    }
}

---

제출 화면

사실 내가 즐겨봤던 Joma Tech 채널에 소개됐던 문제랑 완전 똑같은 문제였는데..

거기서 소개된 해결방안을 생각못한게 많이 아쉽다...

내일은 간지나게 문제를 풀 수 있으면 좋겠다.

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