재귀 14번 unpackGiftbox

문제

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

---

입력

giftBox

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

wish

• string 타입의 문자열

출력

• boolean

---

내가 쓴 코드

function unpackGiftbox(giftBox, wish) {
  // TODO: 여기에 코드를 작성합니다.
  /**
   * 1.재귀 함수의 입력값과 출력값 정의하기
   *  - unpackGiftbox : [str], str => boolean
   * 2.문제를 쪼개고 경우의 수를 나누기
   *  - 쪼갤 수 없는 경우 : 빈 배열, 빈 문자열을 입력받은 경우 
   *                  : 해당 선물을 찾지 못한 경우
   *  - 그렇지 않은 경우  : unpackGiftbox(giftBox, wish)
   *   
   * 3.단순한 문제 해결하기 (base case)
   *  - unpackGiftbox([] or []) => false;
   *  - giftBox !== wish => false
   * 4.복잡한 문제 해결하기
   *  - [n1,[for문],n2..[for문]..]
   * 5.코드 구현하기
   *  
   */

  if(giftBox.length === 0 || wish === ''){
    return false;
  }

  for (let i = 0; i < giftBox.length; i++) {
    if (giftBox[i] === wish) {
      return true;
    }

    if (Array.isArray(giftBox[i])) {
      const result = unpackGiftbox(giftBox[i], wish);
      if (result) {
        return true;
      }
    }
  }
  return false;
  

  
  
  
}

---

어려웠던 점 && KEY

1. for문을 이용해 배열의 요소가 객체인 경우까지 접근을 했다. 하지만 처음 코드를 작성할 때

  

  for (let i = 0; i < giftBox.length; i++) {
    if (giftBox[i] === wish) {
      return true;
    }

    if (Array.isArray(giftBox[i])) {
      return unpackGiftbox(giftBox[i], wish);
     
    }
  }

이런식으로 작성을 했다. 이 경우 giftBox 요소 중 ['a', [], 'b']가 존재하는 경우 false가 리턴되기 때문에 테스트 코스를 통과하지 못한다. 그래서 완전 탐색을 이용해 true값을 얻은 후 return을 할 수 있게 코드를 작성하였다.

완전 탐색은 모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘 이다. 이후 TIL을 통해 자세히 공부를 할 계획이다.