등차수열에서 중간에 빠진 수 구하기 : binary search 기법으로 풀면 된다.

오늘 새벽에 들어온 문제 하나 보겠습니다.

 당연하게도, brr은 오름차순으로 sort가 된 상태입니다. 쉬운 문제는 아닙니다. 다만, 아이디어를 얻을 수 있는 것 중 하나는 이진 검색이라는 것이 있어요. 링크 들어가셔도 좋을 듯 싶어요. 이것을 아신다는 전제하에 설명을 드리도록 하겠습니다.

 

 

---

 먼저, 등차 수열 {a(1), a(2), ... , a(n)}이 있다면 임의의 1< i,j <= n에 대해서 a(i) - a(i-1)과 a(j) - a(j-1)이 같습니다. 중간에 있는 수 하나를 제거했다면, 하나의 차이만 다를 겁니다. 예를 들어서, [1, 3, 5, 7, 9] 에서 중간에 있는 3을 제거했다고 해 봅시다. 그러면, [1, 5, 7, 9]가 될 거에요. 그러면 먼저 어떻게 하는 게 좋을까요?

 

 

 먼저, 원래 수열의 등차를 찾아야 합니다. 이것은 어떻게 찾으면 좋을까요? 원래 수열에서 인접한 것들끼리 차이를 구합니다. 구해보면, 2, 4, 2가 나옵니다. 여기서 2는 2번 나왔으므로, 원래 등차인 d 값은 2임을 알 수 있어요. 그런데 전체를 돌아봐야 알 수 있는 것일까요?

 

 

 아닙니다. 앞에 4개의 원소만 보고도 알 수 있습니다. 왜냐하면, 원래 등차인 d값과, 수가 빠진 등차 t의 값을 보았을 때, t값은 단 1번만 나타나기 때문입니다. 그러면, 최악의 경우라도, 구간 [0, 3]을 보면 가려낼 수 있을 거에요. 예를 들자면, 노란색으로 칠한 부분을 봅시다.

 

 

이 경우, 각각 차이가 2, 4, 2입니다. 이 중 2는 2번, 4는 1번 나왔으므로, 원래 d값은 2가 됩니다. 만약에 구간 [0,3]을 보았는데, arr[1] - arr[0]과 arr[2] - arr[1]과 arr[3] - arr[2]가 모두 같았다. 그렇다면 말할 것도 없이 d값은 arr[1] - arr[0]입니다. 핵심은 저 셋 중에 최소한 하나의 값과 d는 일치한다는 것입니다.

 

 

 그러면 d값은 어떻게 찾으면 될까요? 간단합니다. 1번째 인접 원소의 차이를 a, 2번째 차이를 b, 3번째 차이를 c라고 해 봅시다. a와 b가 같다면 더 볼 필요도 없습니다. 그렇지 않다면 a와 b가 다른 경우입니다.

 

 

 그러면, A, B, A꼴로 가는 경우가 있고, A, B, B 꼴로 가는 2가지 경우가 있을 겁니다. a == c인 경우 위 그림과 같이 갈 겁니다. 따라서, a의 값을 리턴합니다. 만약에 b와 c가 같다면 아래 그림과 같이 갈 거에요.

 

 

 그러면, 이 경우 a값이 아닌 b값을 리턴하면 될 거에요.

 

 

 그러면 대충 이런 식으로 코딩을 하실 수 있을 거에요. 여기까지는 그렇게 크게 어렵지 않아요.

 

 

---

 그러면, 기저를 어떻게 잡고, 범위를 어떻게 좁혀 나갈 것인지가 문제입니다. 사실 서론에 이미 스포일러 해 버렸죠. binary search를 아신다는 전제하에 설명 드리겠다고요. 결국 O(n)의 복잡도에 계산을 하지 않으려면, 반으로 쪼개던지, 한 번에 구하던지 해야 할 것인데요. 반으로 쪼개면 규칙을 찾을 수 있을까요? le = 0, ri = 7인 사례를 예로 들어 봅시다.

 

 

 mid 값을 (le + ri)/2로 계산한다면, mid 값은 (0 + 7) / 2 = 3일 겁니다. 그러면 le ~ mid까지 구간의 갯수는 3이고, mid ~ ri까지의 구간 갯수는 ri - mid일 겁니다. 그러면 수가 하나 빠진 것은 어떻게 알아낼까요? 예를 들어 왼쪽에서 수가 하나 빠졌다고 해 봅시다.

 

 

 그러면 우측에서 수가 하나 이상 빠질 수 있을까요? 아닙니다. 반대로, 왼쪽에서 수가 하나도 빠지지 않았다면, 우측에서 수가 하나 빠져야 합니다. 즉, a + b = 1이고 a >= 0이고 b >= 0일 때, a = 0이고 b = 1이거나, 혹은 a = 1이고 b = 0이여야 합니다. 그러면, 좌측에서 수가 빠지지 않았다면, 우측에서 탐색을 해야 하고, 반대로, 좌측에서 수가 빠졌다면, 왼쪽 구간을 탐색해야 할 거에요. 데이터를 볼까요?

 

 

 문제를 보면, arr[mid] - arr[le]의 값은 8입니다. 구간 갯수는 3입니다. d 값은 2입니다. 2와 3을 곱한 값 6은 8과 같지 않습니다. 따라서, 이 때에는 왼쪽을 탐색해야 합니다.

 

 

 반면에 이 경우는 어떤가요? arr[mid] - arr[le]의 값은 6이고, 구간 갯수 3, d 값은 2. 2와 3을 곱한 값 6은 6과 같아요. 따라서 오른쪽 구간을 탐색하면 됩니다. 이것을 그대로 코드로 옮기면 아래와 같아요.

 

 

 19번째 줄도 바뀌었다는 것을 알 수 있는데요. 기저 조건에 대해서는 브루트 포스하게 구하기 위해서입니다. 예를 들어, 구간의 길이가 4인 경우에는 그냥 4번만 돌리고도 간단하게 찾을 수 있어요.

 

 

 위 그림에서 27 ~ 30번째 줄이 그러한 일을 수행합니다. ret_rm_num 함수의 시간 복잡도는 O(log(n))이 됩니다.