알고리즘: 중첩된 배열과 재귀함수

문제

선물 상자에 대한 정보를 담은 배열과 문자열을 입력받아 조건에 맞는 선물이 있는지 여부를 리턴해야 합니다.

입력

인자 1 : giftBox

• 문자열, 배열을 요소로 갖는 재귀적으로 정의된 배열 (입출력 예시 참고)
• 문자열은 선물 상자에 들어있는 각 선물의 이름을 의미합니다.
• 배열은 더 작은 선물 상자를 의미합니다.

인자 2 : wish

• string 타입의 문자열

출력

• boolean 타입을 리턴해야 합니다.

주의 사항

• 함수 unpackGiftbox는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용이 가능합니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 빈 배열 또는 빈 문자열을 입력받은 경우, false를 리턴해야 합니다.

입출력 예시

const giftBox = ['macbook', 'mugcup', ['eyephone', 'postcard'], 'money'];

let output = unpackGiftbox(giftBox, 'iphone');
console.log(output); // --> false

output = unpackGiftbox(giftBox, 'postcard');
console.log(output); // --> true

function unpackGiftbox(giftBox, wish) {
  // recursive case
  for (let i = 0; i < giftBox.length; i++) {
    if (giftBox[i] === wish) {
      return true;
    } else if (Array.isArray(giftBox[i])) {
      const result = unpackGiftbox(giftBox[i], wish); 
	 //그냥 return result를 작성하면 중첩된 배열로 계속 파고들어서 빠져나오지 못한채 false를 리턴한다. 다음번 배열 혹은 요소를 순회하지 못한다.
      if (result){ 
        return true; 
	      }  // 이렇게 wish를 찾는다면 바로 true를 리턴하고 함수가 종료된다.
    }
  }  // 반복문 스코프 끝나는 지점
  // base case
  return false;
}

🔑  재귀함수를 개념을 이해하는데 중요하면서도 쉬운 문제라고 여겨진다.

 다른 풀이 방법 1
 function unpackGiftbox(giftBox, wish) {
   // recursive case
   let anotherBoxes = [];
   for (let i = 0; i < giftBox.length; i++) {
     if (giftBox[i] === wish) {
       return true;
     } else if (Array.isArray(giftBox[i])) {
       anotherBoxes = anotherBoxes.concat(giftBox[i]);
     }
   }
   if (anotherBoxes.length > 0) {
     return unpackGiftbox(anotherBoxes, wish);
   }
   // base case
   return false;
// }

🔑 위 코드를 보면 따로 box를 만들어서 작은 선물상자들을 모두 모은 뒤에

그 박스가 빈 박스가 되기 전까지 재귀 호출을 통해 반복하는 모습을 볼 수 있다.

//  다른 풀이 방법 2 reduce활용
 function unpackGiftbox(giftBox, wish) {
   const result = giftBox.reduce((acc, curr) => {
     if (curr === wish) {
       return true;
     } else if (Array.isArray(curr)) {
       return unpackGiftbox(curr, wish) || acc; // 선물 찾으면 return true;
     } else {
       return acc;  // return false;
     }
   }, false); // initialValue를 false로 제공

   return result;
 }

Reduce사용시 콜백함수의 최초 호출 때 initialValue를 제공한 경우, accumulator는 initialValue와 같고
currentValue 는 배열의 첫 번째 값과 같습니다.

🔑  리듀스 함수 좀 더 다양하게 공부 할 필요 있음. + 맵과 필터도