자바스크립트 개발자 포럼dovelet의 화장실문제를 풀었습니다.
재귀의 분기를 이용해서 풀었습니다. 연산이 많이 필요한 프로그램이긴 합니다만
나름 의미있는 작업이었던 것 같습니다. (트리를 분기시킨다는 점에서요)
문제는 화장실에 소변기가 N개 만큼 있는데,
사람들은 바로 옆에서 볼일을 보는 것이 싫어서
최소한 두칸씩 띄어서 소변을 보게 됩니다.
보통 사람들은 두칸씩만 띄어서 볼일을 보지만
가끔 프라이버시가 중요한 사람들은 3칸씩 띄어서 볼일을 봅니다.
이때 N개의 소변기에서 볼일을 볼 수 있는 가장 많은 사람의 수와, 가장 적은 사람의 수를 알아내야 합니다.
단, 4칸 이상씩은 떨어질 수 없고, 2칸씩이든 3칸씩 떨어져 보든 더이상 볼일 을 볼 수 있는 사람이 없을 때까지
차야합니다.
제가 작성한 전체 코드는 링크를 걸어놨습니다.
일단, 저는 이걸 어떻게 풀어야 할까 고민하다가
''아 모르겠다. 직접 하나하나 한칸씩 가보고, 2칸씩 가보면 되지!!"
이미 좀 제 스스로에게 미안한 마인드로 시작했습니다.
한칸한칸 직접 손가락으로 세어볼 수는 없는 노릇이고,
얼마전에 배운 이진트리로 하면 되겠지 생각했습니다.
어짜피, 1칸씩 떨어져 보는 거랑, 2칸씩 떨어져 보는 거 밖에 없고, 모든 경우의 수를 다 구해야 하니
2진트리가 적당해 보였습니다.
준비물
그래서 일단 준비물부터 모아보았습니다. (가이드북을 보니, 재료는 위에 모아두는 것이 관리하기 편하다고 하네요)
var n = 11; //변기의 개수
var toiletTub = Array(n); //배열을 n개 만큼 선언한다.
toiletTub.fill(true); //true로 채운다.
var counts = [], counts2 = [], counter = 0, counter2 = 0; //2개씩 있는 이유는, 첫번째 변기부터와, 2번째 변기부터 볼일을 보는 경우의 수를 고려한 것이다.
var index = 0; //배열의 인덱스
첫번째로 소변기의 개수를 알아야 할 것이고, 소변기의 끝에 가서 순회가 종료되기 위해 배열은 true로 설정합니다.
counts, counts2, 그리고 counter, counter2가 따로 준비했는데 2개를 준비한 이유는
2가지 분기로 나뉘기 때문입니다.
첫번째는 첫번째 칸부터 볼일을 볼때이고, 2번째는 2번째 칸부터 볼일을 볼 때인데,
2가지로 분기를 나눈이유는 어떠한 경우에도 3번째 칸부터 볼일을 보지 않기 때문이고,(그러면 첫번째 칸에 사람이 볼일을 봐야만 하니까)
또, 첫번째 칸부터 볼일을 보면 최대인원수가 볼일을 볼 수 있을 것이고, 두번째 칸부터 볼경우에 볼일 을 볼 수 있는
최소한의 인원이 나올 것이라고 생각했기 때문입니다.
그래서 2분기는 서로 다른 counts, counts2 배열과, counter, counter2 변수를 가집니다.
마지막으로 toiletTub 배열의 위치를 체크할 index 변수를 가집니다.
도구 만들기
일단 처음에 한 일은, 2진트리를 만들어야하니, 트리를 구성할 때 필요한 간단한 도구를 만들었습니다.
var treeTool = {
goTwoSpace: function(currentTreeIndex){ //오른쪽으로 2칸 가서 오줌누기
return currentTreeIndex + 2;
},
goThreeSpaces: function(currentTreeIndex){ //오른쪽으로 3칸 가서 오줌누기
return currentTreeIndex + 3;
}
}
경우의 수는 두가지입니다. 첫번째는 2칸 넘어가서 볼일을 보는 경우와, 3칸가서 볼일을 보는 것입니다.
그래서 2칸 옆의 소변기의 위치와, 3칸 옆의 소변기 위치를 반환하는 함수를 treeTool모듈에 담았습니다.(인자는 현재 인덱스)
순회
function traveler (toiletTub, index, counter){
if(!toiletTub[index]){ //만약 변기 개수를 초고화여 오줌을 누려할경우
return counts.push(counter); //지금까지 변기에서 오줌누고 있는 사람의 수를 counts에 넣는다.
}
//2번째 변기에서 시작할 경우
function traveler2 (toiletTub, index, counter){ //굳이 밖에다가 따로 만들필요 없이 내부에서 함수를 돌린다.
if(!toiletTub[index]){ //만약 변기 개수를 초과하여 오줌을 누려할 경우
if(index === 1) ++counter; // 첫번째로 오줌을 누고 다른 변기에 오줌을 싸지 못할경우
return counts2.push(counter); // 지금까지 변기에서 오줌누고 있는 사람수를 counts2에 넣는다.
}
++counter; //다른 분기로 나아갈 때마다, 오줌 누는 사람을 추가한다.
traveler2(toiletTub, treeTool.goTwoSpace(index), counter); //두칸 옆으로 가본다.
traveler2(toiletTub, treeTool.goThreeSpaces(index), counter); //세칸 옆으로 가본다.
}
//2번째 변기에서 시작할 경우
if(index === 0 ){
traveler2(toiletTub, index + 1, counter2); //함수를 실행시킨다. counts2 는 외부에 있으므로 상관 없다.
}
++counter; //다른 분기로 나아갈 때마다, 오줌 누는 사람을 추가한다.
traveler(toiletTub, treeTool.goTwoSpace(index), counter); // 두칸 옆으로 가본다.
traveler(toiletTub, treeTool.goThreeSpaces(index), counter); // 세칸 옆으로 가본다.
}
위의 복잡해 보이는 트리를 통해 구현이 됩니다.
간단하게 설명하자면 아래의 간단한 그림과 같습니다. 숫자는 변기 위치(index) 입니다.
0 1
2 3 3 4
4 5 5 6 5 6 6 7
6 7 ............ 7 8 .............
트리가 이런식으로 0번째 인덱스에서 시작하지만, 시작과 동시에 1번 인덱스에서 새로운 트리가 만들어집니다.
레벨을 한칸 내려갈 때마다 counter에 추가를 하고, 인덱스가 undefined가 나올 경우 counts, counts2 배열에 지금까지
카운트한 counter, counter2를 집어 넣고 반환시킵니다.
이렇게 모아진 counts, counts2안의 순회 횟수들에서 최대값과 최소값을 구할경우
답을 얻을 수 있다고 판단했습니다.
최대값, 최소값 구하기
간단한 함수로 최대값과 최소값을 구했습니다.
function countMaxAndMin (count, count2){
var max = 0, min = count2[0], i = 0, j = 0;
for(; i < count.length; ++i){
if(count[i] >= max){
max = count[i];
}
}
for(; j < count2.length; ++j){
if(count2[i] <= min){
min = count[i];
}
}
return (function(){
var map = new Map();
map.set('max', max);
map.set('min', min);
return map;
})();
맵으로 리턴 했다 이외에는 딱히 설명은 필요 없어 보이네요.
실행
위에 준비한 함수들들을 실행시켜 답을 구합니다.
traveler(toiletTub, index, counter); //함수콜 한방에 2가지 값을 모두 구할 수 있다.
var result = countMaxAndMin(counts, counts2);
for(let [key, val] of result){
console.log(`${key} is ${val}`);
}
원래는 분기를 따로 나누어 traveler 와 traveler2를 따로 실행시켜 각각 답을 얻었습니다만,
내부적으로 재귀를 분기시키니 함수 한방으로 2가지 값을 모두 구할 수 있었습니다.
후기
조금더 코드의 개선의 필요성을 느끼긴 합니다. n값을 100으로만 집어 넣어도 스택이 넘쳐 버려서 중단이 되네요.
그렇지만 나름 재미있는 문제였던 것 같습니다.
조금더 간단하게 풀려고 노력을 해봐야 겠습니다. 이 문제에 70줄이 넘어가는건 조금 오바인듯