•
문제 설명 : 중복되는 숫자 찾기
•
풀이 방법
◦
길이가 n + 1인 배열에 1 ~ n 범위의 숫자로 이루어진 요소가 들어있다.
◦
이때 중복되는 하나의 숫자를 찾으면 된다.
•
시간복잡도 :
•
성공 코드
가장 간단한 방법은 set 을 사용하는 방법이다.
하지만 이 방법은 공간 복잡도도 O(N)이기 때문에, 완전히 최적화된 방법이라고 하기는 어렵다.
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
info = set()
for num in nums:
if num in info:
return num
info.add(num)
Python
복사
•
성공 코드(O(N))
솔루션을 보니, 플루이드 순환 찾기 알고리즘을 사용하였다.
배열에 들어가는 요소가 1 ~ n range이기 때문에, 인덱스 번호와 매핑해서 사용하라는 힌트였던 것 같다.
즉, “배열의 요소가 인덱스 번호와 유사하면 인덱스 번호를 사용하는 문제일 가능성이 높다”
보통은 그래프의 노드 이동 거리를 다르게 하여 처리했다면, 이번에는 인덱스 탐색 depth를 조절하여 처리하였다.
즉, 요소는 인덱스 번호를 나타내며 “인덱스 번호의 사이클을 찾는다” 와 같은 느낌인 것이다.
# slow는 1-depth, fast는 2-depth
slow = nums[slow]
fast = nums[nums[fast]]
Python
복사
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = nums[0]
fast = nums[0]
while True:
# slow는 1-depth, fast는 2-depth
slow = nums[slow]
fast = nums[nums[fast]]
# 동일 값, 노드로 따지면 순환 시작 노드
if slow == fast:
break
# 첫 인덱스로 이동
slow = nums[0]
# 동일 값이 될때까지 진행
# fast, slow가 만났던 지점 -> 사이클 시작 거리
# head -> 사이클 시작 거리
# 위 2개가 같다는 것이 플로이드 순환 탐지의 공식이다.
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Python
복사