[leetcode][645] Set Mismatch

문제 : leetcode.com/problems/set-mismatch/

---

1~n 까지 모든 정수를 포함하는 배열이 있다. 오류로 인해 숫자 하나가 1~n 중 다른 숫자로 변경되었다.

즉, 변경된 배열에는 누락된 숫자와 중복(2번 발생)된 숫자가 존재한다.

변경된 배열이 주어질 때 중복된 수와 누락된 수를 구하여라.

---

n크기의 등장횟수를 저장하는 배열을 만든다.

입력 배열을 탐색하면서 등장횟수를 갱신한다.

등장횟수가 2번인 것과 0번인 수가 정답이 된다.

시간복잡도와 공간복잡도 모두 O(N).

---

등장하지 않거나 두 번 등장하는 수가 한 개만 존재한다고 하였기에 비트를 쓰거나 수학적으로 접근이 가능할거 같아서 토론글을 둘러보았다. 그러다 좋은 글 있어서 해당 글  보고 정리한 방법. 따봉따봉

 

학창시절 배운 수학공식

x^2 - y^2 = (x+y)(x-y)

등차수열합(1~n) = n(n+1)/2

거듭제곱합(1^2 ~ n^2) = n(n+1)(2n+1)/6

 

let,

x = 2번 나타난 수

y = 등장하지 않은 수

 

배열의 합 = (1~n의 합) - 등장하지 않은 수 + 2번 나타난 수 
        = n(n+1)/2 - y + x
        
x - y = n(n+1)/2 - 배열의 합 = let, A

제곱 배열의 합 = (1^2 ~ n^2의 합) - 등장하지 않은 수의 제곱 + 2번 나타난 수의 제곱
        = n(n+1)(2n+1)/6 - y^2 + x^2

x^2 - y^2 = n(n+1)(2n+1)/6 - 제곱 배열의 합 = let, B

A 식의 양변에 (x+y)를 곱해준다.

(x - y)(x + y) = A(x+y)

이는 x^2 - y^2 와 같기 때문에 B와 같아진다.

 

즉,

A(x+y) = B
x + y = B/A

 

x+y = B/A

x-y = A

 

// 두 식을 더한다.
2x = A + B/A
x = (A + B/A)/2

// 두 식을 뺀다.
2y = B/A - A
y = (B/A - A)/2

 

x, y를 제외한 모든 수들은 입력값에서 구할 수 있으므로 A, B를 구한 뒤 위 수식에 대입하면 x, y를 구할 수 있다.

 

시간복잡도는 동일하게 배열을 한 번 탐색해야 하므로 O(N)이지만 공간복잡도는 O(1)로 줄어든다.

---

소스코드 

space O(N) : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/645.%20Set%20Mismatch.cpp

space O(1) : github.com/fpdjsns/Algorithm/blob/master/leetcode/easy/645.%20Set%20Mismatch(math).cpp

 

참고

leetcode.com/problems/set-mismatch/discuss/1089475/Python-O(n)-timeO(1)-space-math-solution-explained