m := N/2라고 하고 A[m] < B[m]이었다고 가정합시다. 반대의 경우도 비슷합니다.
- 사실 1. 각 1 <= i <= m에 대해서 A[i]보다 크거나 같은 수는 A와 B를 합쳐서 최소 N+1개 있습니다. (A[m+1] ~ A[N], B[m] ~ B[N])
- 사실 2. 각 m < i <= N에 대해서 B[i]보다 작거나 같은 수는 A와 B를 합쳐서 최소 N개 있습니다. (A[1] ~ A[m], B[1] ~ B[m])
따라서 A와 B를 합쳐서 정렬하면 A[1] ~ A[m]는 N번째 원소보다 왼쪽에, B[m+1] ~ B[N]은 N번째 원소보다 오른쪽에 옵니다. A[1] ~ A[m]과 B[m+1] ~ B[N]을 제외했을 때의 중앙값은 원래의 중앙값과 같습니다.

ksjb2897 1년 전
저는 이 문제를
배열 A의 포인터를 하나 만들어서 m1, 배열 B의 포인터를 하나 만들어서 m2로 만들고,
A[m1]과 B[m2]를 비교하여, 이 둘의 대소관계가 바뀌는 경계선을 이분탐색으로 찾은 후, 경계선에 있는 4개의 값(배열 A에서 2개의 값, 배열 B에서 2개의 값)을 비교하여 중앙값을 찾았습니다.
이 때, m1 + m2 = N을 유지하면서 찾았습니다.
그렇게 하다보니 예외처리가 많아지고 코드가 좀 복잡해졌는데, 다른 사람들 풀이 보니까 정말 간단하더라구요.
다른사람들도 어쨋든 A[m1]과 B[m2]의 대소관계를 비교하면서 푼 것 같은데, 어떻게 예외처리 없이 푼지 모르겠습니다.. 대소관계를 푼다는 것은 어쨋든 대소관계가 바뀌는 경계선만 남긴다는 것인데, A[m1]>B[m2]인 m1과 m2에 중앙 값이 있을 수도 있고, A[m1]<B[m2]인 m1과 m2에 중앙 값이 있을 수도 있는데, 이 들을 모두 비교없이 어떻게 중앙값을 판단하죠...??
추가로 저는 캐싱을 이용하여 aa[SIZE], bb[SIZE]를 만들어서 중복되는 쿼리를 줄임으로써 메모리를 대략 2^20정도를 더 썼는데, 왜 남들과 메모리 사용량이 더 적거나 비슷한지 궁금합니다....남들은 메모리 안쓰는데 말이죠..