[leetcode][442] Find All Duplicates in an Array

문제 : https://leetcode.com/problems/find-all-duplicates-in-an-array/

---

배열크기가 n 일때, 1이상 n이하의 값을 가지는 int형 배열이 주어진다.

배열 요소들은 한 번 혹은 두 번 존재한다. 주어진 배열에서 두 개가 있는 요소들을 구해라.

---

주목해야 할 점은 배열의 요소들이 1 이상 n 이하라는 점이다. 이를 이용하여 nums배열 값들을 해당 인덱스 위치(nums[i] - 1)에 이동시킬 수 있다. ex) [1,3,4,2] -> [1,2,3,4]

 

주어진 배열을 앞에서부터 탐색하면서 nums[i] 위치에 i+1 수가 올때까지 다른 요소값과 교환한다.

그러기 위해서는 nums[i]에 있는 수를 nums[i] 인덱스 위치에 있는 수와 swap한다.

예를 들어 nums[i] 값이 4라면 인덱스3(= nums[i]-1. 인덱스는 zero based 이기 때문)에 있는 값과 4를 교환한다.

nums[i]와 nums[nums[i]-1]] 가 같은 수라면 위 알고리즘으로는 무한반복에 빠질 수 있기 때문에 같은 경우 반복문을 종료해야한다.

for (i = [0..nums.size)):
  let, ind = i
  while(nums[ind] != ind+1): // ind 위치에 인덱스에 해당하는 수(ind+1)가 올때까지 반복
    if(nums[ind] == nums[nums[ind]-1]): while문 종료 (무한반복 방지)
    swap(nums[ind], nums[nums[ind]-1]) (수 교환)

수도코드로 표현하면 위와 같다.

[4, 3, 2, 7, 8, 2, 3, 1]

[3, 2, 3, 4, 8, 2, 7, 1] // i=0
[3, 2, 3, 4, 8, 2, 7, 1] // i=1
[3, 2, 3, 4, 8, 2, 7, 1] // i=2
[3, 2, 3, 4, 8, 2, 7, 1] // i=3
[1, 2, 3, 4, 3, 2, 7, 8] // i=4
[1, 2, 3, 4, 3, 2, 7, 8] // i=5
[1, 2, 3, 4, 3, 2, 7, 8] // i=6
[1, 2, 3, 4, 3, 2, 7, 8] // i=7

예제를 위 알고리즘으로 돌리면 배열은 위와 같이 변경된다.

모든 인덱스를 돌면서 배열이 세팅되었을 때 nums[i] = i+1 이 안되는 경우 nums[i] 수가 두 번 존재하는 수가 된다.

위 예제에서는 i=7 일 때 배열에서, 3(nums[4]), 2([nums[5])가 이에 속하며 이를 리스트에 넣어주면 정답이 된다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/442.%20Find%20All%20Duplicates%20in%20an%20Array.cpp