[1스4코2파] # 198 LeetCode 287. Find the Duplicate Number

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (198차)
[4코1파] 2023.01.13~ (190일차)
[1스4코1파] 2023.04.12~ (101일차)
[1스4코2파] 2023.05.03 ~ (79일차)

Today :

2023.07.20 [198일차]
linked list
287. Find the Duplicate Number

287. Find the Duplicate Number

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

문제 설명

각 정수가 [1, n] 범위에 있는 n + 1 정수를 포함하는 정수 nums의 배열이 주어질때, 반복되는 숫자가 1개가 존재하는데 이 반복되는 숫자를 반환함. 배열 번호를 수정하지 않고 문제를 해결해야 하고 일정한 추자 공간만 사용해야 한다.

문제 풀이 방법

풀이방법은 O(n) 이면 set을 이용해 푸는 방법이 있겠고,
다른 방법으로는 플로이드 워셜 알고리즘이 있다.
Floyd's cycle detection 알고리즘으로 푸는 방법..

내 코드

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        slow, fast = 0,0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
            
        slow2 = 0
        while True:
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2:
                return slow

증빙

여담

플로이드 순환 알고리즘은 또 뭔데 그뭔씹..