.leetcode(287. Find the Duplicate Number)

문제

https://leetcode.com/problems/find-the-duplicate-number/

문제 풀기 전

1. 제한조건을 부분적으로 만족한다면 HashSet으로 풀어 볼 수 있다.
2. 제한조건을 부분적으로 만족한다면 Arrays.sort으로도 풀어 볼 수 있다.

직접 푼 풀이

소요시간:

#HashSet 풀이
class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for(int i=0; i<nums.length; i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            } else {
                set.add(nums[i]);
            }
        }

        return 0;
    }
}

#Arrays.sort
class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);

        int compare = nums[0];
        for (int i=1; i<nums.length; i++) {
            if (compare == nums[i]) {
                return nums[i];
            }
            compare = nums[i];
        }

        return 0;
    }
}

느낀점

1. 'Floyd's Tortoise and Hare'는 링크드 리스트에서만 된다고 생가했는데 이게 배열에서도 된다는걸 알게되었다. 그리고 이번에 제대로 구현까지 해봤다.
2. 아래 풀이에서 잘 보면 2번의 while이 나온다. 첫번째는 같은곳에서 만나는걸 구하는 루프이다. 이건 그럭저럭 이해가는데 2번재 루프가 처음에 이해가 안갔다. 어떻게 저런공식이 나오는거지 했는데 고민 끝에 확실히 알았다.
   

   

• 위에처럼 정의하고 만남지점까지의 거리를 식으로 표현해보자
  • 토끼가 간 거리는 M+P*L+K 이렇게 나타낼 수 있고 (P=토끼가 고리를 순환한 수)
  • 거북이가 간 거리는 M+Q*L+K 이렇게 나타낼 수 있다. (Q=거북이가 고리를 순환한 수)
  • 토끼는 거북이가 간 거리의 2배이므로 식으로 이렇게 정리해볼 수 있다.
  • M+PL+K = 2(M+Q*L+K) 이걸 이제 정리해보면
  • (P-2Q)*L = M + K 가 되는데 이 말은 즉 M+K의 거리가 곧 순환 고리의 갯수 L의 배수라는 의미이다.
  • 즉 다시 말해 토끼와 거북이가 만난 지점과 출발지점(nums[0]인 지점)에서 각각 속도를 1로 출발한다면 만날 수 밖에 없다는 뜻이다.
  • 따라서 해당지점을 지나기전에 반드시 만나는 지점이 바로 순한이 시작하는 점이라는 것이다.
• 이 부분이 너무 궁금했는데 유투브(아래 참고에 링크가 있다) 외국인이 아주 잘 설명해주어서 나도 그걸로 이해했고 그걸 풀어설명한 것이다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    public int findDuplicate(int[] nums) {

        int tortoise = nums[0];
        int hare = nums[0];

        while(true) {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];

            if (tortoise == hare) {
                 break;
            }
        }

        tortoise = nums[0];
        while(true) {
            if (tortoise == hare) {
                return tortoise;
            }
            tortoise = nums[tortoise];
            hare = nums[hare];
        }       
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

참고

• Floyd's Tortoise and Hare: https://www.youtube.com/watch?v=LUm2ABqAs1w