세 배열 병합하기
예전에 코딩 면접에서 정렬되어 있는 배열 세 개를 병합하는 함수를 구현하라는 문제가 주어진 적이 있다. 한 번에 배열 세 개를 병합하려면 복잡할테니, 배열 두 개를 먼저 병합한 다음 그걸 세 번째 배열과 병합하겠다고 했다. 면접관은 그냥 배열 세 개를 직접 병합하는 코드를 작성하라 했다.
세 배열 요소를 비교해가며 병합하려면 코드가 너무 복잡해질 것 같은 걱정이 앞섰다. 복잡성을 회피하기 위한 방법을 생각했지만, 그게 짧은 시간 안에 생각날 리가 없었다. 결국은 버벅거리다가 배열 병합은 시작도 하지 못하고 면접 시간을 모두 써 버리고 말았다. 결과는 당연히 탈락!
세 수를 비교하려면 당장 경우의 수가 많아진다. 여기에 배열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;
}
생각보다 복잡하지 않다. 면접 때 지레 겁을 먹고 포기했던 것이다. 간단히 테스트를 돌려보니 모두 통과한다. 코드에 버그가 숨어 있을지도 모르겠다. 그러나 면접 때 이 정도로 코드를 작성했다면 떨어지지 않았을 것 같다.
교훈: 지레 겁먹고 포기하지 말자. 직접 부딛혀보면 처음 느꼈던 것과 달리 쉬운 경우도 많다.