세 배열 병합하기
예전에 코딩 면접에서 정렬되어 있는 배열 세 개를 병합하는 함수를 구현하라는 문제가 주어진 적이 있다. 한 번에 배열 세 개를 병합하려면 복잡할 테니, 배열 두 개를 먼저 병합한 다음 그걸 세 번째 배열과 병합하겠다고 했다. 면접관은 그냥 배열 세 개를 직접 병합하는 코드를 작성하라 했다.
세 배열 요소를 비교해 가며 병합하려면 코드가 너무 복잡해질 것 같은 걱정이 앞섰다. 복잡성을 회피하기 위한 방법을 생각했지만, 그게 짧은 시간 안에 생각날 리가 없었다. 결국은 버벅거리다가 배열 병합은 시작도 하지 못하고 면접 시간을 모두 써 버리고 말았다. 결과는 당연히 탈락!
세 수를 비교하려면 당장 경우의 수가 많아진다. 여기에 배열 1이 먼저 끝난 경우, 배열 2가 먼저 끝난 경우, 배열 3가 먼저 끝난 경우, 배열 1, 2가 끝난 경우, 배열 2, 3이 끝난 경우 등의 조합도 고려해야 할 것이다. 아마도 면접관은 이런 복잡성을 어떻게 다루는지 보고 싶어 했던 게 아닐까.
갑자기 이 문제가 생각나, 다시 풀어보고 싶어졌다. 무식하게 모든 경우의 수를 다 처리하도록 코드를 작성하면 되는 것 아닌가. 경우의 수가 많아진다고 해도 그게 수십 수백 가지가 아니라면 코드도 지나치게 복잡해지지는 않으리라.
함수는 다음과 같은 모양이 될 것이다.
int[] merge3(int[] xs, int[] ys, int[] zs) {
int[] merged = new int[xs.length + ys.length + zs.length];
int i = 0, j = 0, k = 0;
for (int n = 0; n < merged.length; n++) {
// ...
}
return merged;
}
i는 배열 xs, j는 배열 ys, k는 배열 zs를 위한
인덱스다. n은 배열 merged를 위한 인덱스다. 여기까지 코드를 써놓고
생각해 보니, 각 배열의 요소를 비교해서 가장 작은 값만 알아내면 그만
아닌가. 면접 때는 이 부분을 너무 복잡하게 생각했는데, 지금 생각해 보니
그냥 if 세 번이면 끝난다. 즉,
xs[i]가 가장 작으면 이걸merged[n]에 넣고i를 증가ys[j]가 가장 작으면 이걸merged[n]에 넣고j를 증가zs[k]가 가장 작으면 이걸merged[n]에 넣고k를 증가
하면 되는 것이다. 이걸 코드로 옮기면 다음과 같다.
int[] merge3(int[] xs, int[] ys, int[] zs) {
// ...
for (int n = 0; n < merged.length; n++) {
// ...
if (xs[i] <= ys[j] && xs[i] <= zs[k]) {
merged[n] = xs[i++];
} else if (ys[j] <= xs[i] && ys[j] <= zs[k]) {
merged[n] = ys[j++];
} else {
merged[n] = zs[k++];
}
}
return merged;
}
아직 해야 할 일이 남아 있다. 세 배열 중 하나 또는 둘의 처리가 끝난
경우도 고려해야 한다. 먼저 xs가 끝난 경우부터 처리해 보자. i가
xs.length와 같다면 xs를 merged에 모두 병합했다는 뜻이다.
이 상태에서 ys도 모두 병합했다면 zs를 계속 병합해 주면 된다. ys
병합은 안 끝났지만 zs 병합이 끝났다면 ys를 계속 병합해 주면
된다. ys, zs 모두 병합이 안 끝났다면 두 배열 요소를 비교해
merged로 병합하고 병합한 배열의 인덱스를 증가하면 된다. 이걸 코드로
옮기면 다음과 같다.
int[] merge3(int[] xs, int[] ys, int[] zs) {
// ...
for (int n = 0; n < merged.length; n++) {
// ...
if (i >= xs.length) {
if (j >= ys.length) {
merged[n] = zs[k++];
} else if (k >= zs.length) {
merged[n] = ys[j++];
} else if (ys[j] < zs[k]) {
merged[n] = ys[j++];
} else {
merged[n] = zs[k++];
}
continue;
}
// ...
}
return merged;
}
xs를 먼저 확인했는데, 다음과 같이 ys와 zs를 확인하는 if를 추가할 수 있다.
int[] merge3(int[] xs, int[] ys, int[] zs) {
// ...
for (int n = 0; n < merged.length; n++) {
// ...
if (i >= xs.length) {
// ...
continue;
}
if (j >= ys.length) {
if (i >= xs.length) { // (1)
merged[n] = zs[k++];
continue;
}
if (k >= zs.length) {
merged[n] = xs[i++];
continue;
}
if (xs[i] < zs[k]) {
merged[n] = xs[i++];
} else {
merged[n] = zs[k++];
}
continue;
}
if (k >= zs.length) {
if (i >= xs.length) { // (2)
merged[n] = ys[j++];
continue;
}
if (j >= ys.length) { // (3)
merged[n] = xs[i++];
continue;
}
if (xs[i] < ys[j]) {
merged[n] = xs[i++];
} else {
merged[n] = ys[j++];
}
continue;
}
// ...
}
return merged;
}
코드가 조금 길지만, i, j, k, xs, ys, zs 순서만 바뀌었을 뿐
구조는 똑같다. 그런데 IDE 정적 분석기가 위에 // (1), // (2), // (3)으로 주석을 단 if의 조건이 항상 false라는 점을 알려준다.
가만 살펴보니 맞는 말이다. 이미 같은 조건을 이전 if에서
확인했다. 주석으로 표시한 행으로 왔다는 것은 그 조건이 false임을
뜻한다. 따라서 if문은 (1)을 삭제할 수 있다. (2), (3) if문도
마찬가지로 삭제할 수 있다.
정리된 전체 코드는 다음과 같다.
int[] merge3(int[] xs, int[] ys, int[] zs) {
int[] merged = new int[xs.length + ys.length + zs.length];
int i = 0, j = 0, k = 0;
for (int n = 0; n < merged.length; n++) {
if (i >= xs.length) {
if (j >= ys.length) {
merged[n] = zs[k++];
} else if (k >= zs.length) {
merged[n] = ys[j++];
} else if (ys[j] < zs[k]) {
merged[n] = ys[j++];
} else {
merged[n] = zs[k++];
}
continue;
}
if (j >= ys.length) {
if (k >= zs.length) {
merged[n] = xs[i++];
continue;
}
if (xs[i] < zs[k]) {
merged[n] = xs[i++];
} else {
merged[n] = zs[k++];
}
continue;
}
if (k >= zs.length) {
if (xs[i] < ys[j]) {
merged[n] = xs[i++];
} else {
merged[n] = ys[j++];
}
continue;
}
if (xs[i] <= ys[j] && xs[i] <= zs[k]) {
merged[n] = xs[i];
i++;
} else if (ys[j] <= xs[i] && ys[j] <= zs[k]) {
merged[n] = ys[j];
j++;
} else {
merged[n] = zs[k];
k++;
}
}
return merged;
}
생각보다 복잡하지 않다. 면접 때 지레 겁을 먹고 포기했던 것이다. 간단히 테스트를 돌려보니 모두 통과한다. 코드에 버그가 숨어 있을지도 모르겠다. 그러나 면접 때 이 정도로 코드를 작성했다면 떨어지지 않았을 것 같다.
교훈: 지레 겁먹고 포기하지 말자. 직접 부딪혀보면 처음 느꼈던 것과 달리 쉬운 경우도 많다.