TL;DR: 코딩 테스트의 코드가 수십 줄에 불과하더라도, 디버깅을 우습게 보면 안 된다. 특히나, 재귀적인 솔루션은, 디버깅이 어렵기 때문에, 더욱 그렇다. 이때, 모듈로 분리하고 추상화하여, 모듈 단위로 테스트하면, 디버깅이 쉬워지는 경험을 할 수 있다.
코딩 테스트를 매주마다 치르고있는데 저번 주에 비해서, 이번 주 문제들은 전반적으로 쉬웠고 한 문제도 틀리지 않고 전부 다 맞히겠다는 생각으로 임했다. 하지만, 이는 나의 자만이었고, 한 문제에 1시간 반을 쏟는, 말도 안되는 실수를 하고 말았다... 그로 인해 만점의 꿈은, 내 멘탈과 함께, 바스락바스락 부서졌다.
해당 문제는, 조합을 사용해서 풀면 쉽게 풀리는 문제였음에도, 디버깅에 실패하여 풀어내지 못했다. 몇 줄 되지도 않는 코드의 디버깅인데, 왜 그리 어려웠던 걸까? 그 이유는, 재귀적인 솔루션이었기 때문이다. 반복적으로 드는 생각이지만, 재귀적인 솔루션은, 짧더라도 디버깅이 어려운 경우가 많다. 이제부터, 해당 문제와 내가 작성한 코드를 살펴보자.
문제
생일잔치에 친구들을 초대해서 잔치를 하려고 합니다.
요리를 잘 하지 못해서 배달을 하려고 하는데 배달 가능한 요리 목록들중 친구들의 취향에 따라 못먹는 음식이 있습니다.
모든 친구들의 적어도 한가지 이상의 음식을 먹을수 있도록 주문하기 위한 주문 방법중 요리 개수가 가장 적은 경우의 음식 개수를 리턴하는 함수를 작성하세요.
입력
친구들의 이름이 들어있는 배열 Frineds
각 메뉴별로 음식을 먹을수 있는 친구들의 이름이 적힌 2차원 배열 Taste
출력
친구들의 취향을 만족 시키는 최소한의 음식 주문 개수
예를들어 아래의 매개변수가 입력 되었을 때에는 4번 메뉴(bob, bobby)와 6번 메뉴(andrew, ant)를 주문시 친구 4명의 취향을 모두 만족 시키기 때문에 최소 주문 수는 2개가 된다.
Friends = ['bob', 'andrew', 'bobby', 'ant']
Taste = [['bobby', 'ant'], ['bob', 'ant'], ['bob'], ['bob', 'bobby'] ,['andrew', 'bobby'], ['andrew', 'ant']]
매개변수 : String[] Friends, String[][] Taste
리턴타입 : int방법1
function solution(Friends, Taste) {
function combinationImplementation(Taste, currentIndex, originalTaste) {
let isSatisfied = true;
let collision = new Map();
let currentCombination = originalTaste.slice(0, currentIndex);
Friends.forEach((friend) => collision.set(friend, 0));
currentCombination.forEach((food) => {
food.forEach((friend) => {
collision.set(friend, 1);
});
});
collision.forEach((v, friend) => {
if (v === 0) isSatisfied = false;
});
// 여기까지의 코드는 isSatisfied의 값을 구하는 코드.
if (isSatisfied) {
// base case
return currentCombination;
}
//recursive case
let result = [];
for (let i = 0; i < Taste.length; i++) {
let intermediate = combinationImplementation(
Taste.slice(i + 1),
currentIndex + 1,
originalTaste
);
intermediate = intermediate.map((combination) => [combination, Taste[i]]);
result.push(intermediate);
}
result.sort((a, b) => a.length - b.length);
return result[0];
}
return combinationImplementation(Taste, 0, Taste).length;
}
나는 방법1을 선택했다.
고려했던, 다른 방법은 아래와 같다.
방법2
- 조합을 별개의 함수로 구현한다.
- 1번의 조합 함수를 사용하여, 모든 음식 주문 조합들을 생성한다.
- 주문 조합들을 iterate 하여, 조건을 충족하는 주문 조합들을 골라낸다.
- 골라낸 조합 중에서, 제일 작은 놈을 반환한다.
방법1과 방법2의 비교
방법1의 코드는, 조합을 구현하는 코드와 크게 다르지 않다. 하지만, 제일 큰 차이점은, base case임을 확인하기 위해 사용하는, isSatisfied의 값을 결정하는 부분이다. 모든 친구를 만족시킬 수 있는, 최소한의 음식 주문 개수를 찾기 위해서, 해당 부분을 작성했다. 문제의 조건을 충족하는 주문의 조합을 체크함으로써, 모든 조합을 생성하지 않고도, 문제를 풀어낼 수 있다. 이 방법에서는, 하나의 함수가 1. 조합을 생성하고 2. 해당 조합이 특정 조건을 충족하는지 체크하는, 두 가지의 일을 한다.
방법2는, 조합 코드와 조건을 체크하는 코드를, 별개의 함수로 분리한다. 하지만 퍼포먼스를 이유로, 방법2를 사용하지 않았다. 방법2는, 어떤 경우에서든, 모든 주문 조합을 생성해야 한다. 하지만, 방법1은 모든 조합을 생성하지 않을 수도 있다. 그래서, 방법1을 선택했다. (각주: 방법1에서 재귀 함수가 더 커지면서, 재귀호출이 더 비싸진다. 그래서 오히려, 방법1의 성능이 더 나쁠 수도 있다.)
하지만, 방법1의 선택은, 디버깅을 어렵게 만드는 원인이 됐다. 방법1의 코드를 살펴보면, 조합의 구현이 틀렸음을 확인할 수 있다. recursive case를 처리하는 로직과 base case를 처리하는 로직, 둘 다 버그가 있다. 해당 코드를 디버깅하면서, 어느 부분에 버그가 있는 건지, 고민해야 했다. 만약 조합을 구현하는 코드와 조건을 체크하는 코드가, 별개의 함수로 분리돼있었다면, 각 함수를 독립적으로 테스트함으로써, 빠르게 버그의 원인을 찾아낼 수 있었을 것이다.
마무리
코딩 테스트를 위한 코드였던 만큼, 로직도 단순하고 코드도 짧다. 하지만, 방법1과 방법2의 비교는, 이렇게 단순한 코드에서조차도, 추상화/모듈화가 디버깅에 영향을 미칠 수 있음을 보여준다.
