재귀 연습문제

take

 

문제

수(num)와 배열을 입력받아 차례대로 num개의 요소만 포함된 새로운 배열을 리턴해야 합니다.

 

입력

 

인자 1 : num

• number 타입의 정수 (num >= 0)

 

인자 2 : arr

• 임의의 요소를 갖는 배열

 

출력

• 순차적으로 num 개의 요소로 구성된 배열을 리턴해야 합니다.

 

주의 사항

• 함수 take는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).

 

입출력 예시

 

let output = take(2, [1, -2, 1, 3]);
console.log(output); // --> [1, -2]

output = take(5, [1, -2, 1, 3]);
console.log(output); // --> [1, -2, 1, 3]

 

나의 코드

 

// 함수 밖에 배열(result)을 만들어서
// num 을 1씩 깎으며 arr의 요소를 하나씩 집어넣는다.

// 함수를 다시 사용하려면 result를 초기화해줘야 한다.

// result를 리턴한 이후에 초기화할 수 있는 방법이 없어서
// result2를 만드는 번거로운 과정이 필요했다.


let result = [];

function take(num, arr) {
  
  if (num === 0 || arr.length === 0) {
    let result2 = result;
    result = [];
    return result2;
  }
  
  result.push(arr.shift())
  return take(num - 1, arr);

}

 

 

레퍼런스 코드

 

function take(num, arr) {

  if (num === 0 || arr.length === 0) {
    return [];
  }

  const head = arr[0];
  const tail = arr.slice(1);

  return [head].concat(take(num - 1, tail));
}

// 기존 배열을 쪼개서 새로운 배열을 리턴한다는 아이디어

 

 

 

 

---

 

 

findMatryoshka

 

문제

러시아 전통인형 마트료시카에 대한 정보를 담은 객체와 수를 입력받아 조건에 맞는 인형이 있는지 여부를 리턴해야 합니다.

 

입력

 

인자 1 : matryoshka

• 'matryoshka', 'size' 속성을 갖는 재귀적으로 정의된 객체 (입출력 예시 참고)
• matryoshka.matryoshka는 null 또는 matryoshka 객체
• matryoshka.size는 중첩될수록 작아집니다.

 

인자 2 : size

• number 타입의 수

 

출력

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

 

주의 사항

• 함수 findMatryoshka는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 입력받은 객체는 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 빈 객체를 입력받은 경우, false를 리턴해야 합니다.

 

입출력 예시

 

const matryoshka = {
  size: 10,
  matryoshka: {
    size: 9,
    matryoshka: null,
  },
};

let output = findMatryoshka(matryoshka, 10);
console.log(output); // --> true

output = findMatryoshka(matryoshka, 8);
console.log(output); // --> false

 

나의 코드

 

// 입력 받은 마트료시카 객체의 size가 입력 받은 size와 같으면 true

// 찾는 size가 나오지 않은 채로,
// 마트료시카의 마트료시카 키 값에 해당하는 밸류가 null 이거나
// 마트료시카 키 자체가 없다면 false

function findMatryoshka(matryoshka, size) {
  
  if (matryoshka['size'] === size) return true; 

  if (matryoshka['matryoshka'] === null || 
      matryoshka['matryoshka'] === undefined) 
      return false;

  return findMatryoshka(matryoshka['matryoshka'], size);
}

 

 

 

---

 

 

unpackGiftbox

 

문제

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

 

입력

 

인자 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) {
  if(giftBox.includes(wish)) return true; // 찾는 것이 있으면 true
  for(let i = 0; i < giftBox.length; i++) {
    if(giftBox[i] !== giftBox.flat()[i]) // 자기 자신과 평탄화한 배열을 비교
      return unpackGiftbox(giftBox.flat(), wish);
  }
  // 여기로 넘어왔다는 건 giftBox랑 giftBox.flat()의 요소가 완전 똑같다는 것. 더 이상 볼 필요 없음
  return false;

 

 

레퍼런스 코드

 

function unpackGiftbox(giftBox, wish) {

  // recursive case
  
  for (let i = 0; i < giftBox.length; i++) {
    if (giftBox[i] === wish) {
      return true;	// 찾는 것이 있으면 true
    } else if (Array.isArray(giftBox[i])) {		// 배열의 요소가 배열이면
      const result = unpackGiftbox(giftBox[i], wish);	// 재귀 호출한 값을 result에 할당
      if (result === true) {
        return true;	// 깊이 들어가서 true를 찾으면 true
      }
    }
  }

  // base case
  return false;	// 다 돌았는데 없으면 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;
// }

// 다른 풀이 방법 2
// 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;
//     } else {
//       return acc;
//     }
//   }, false);
//   return result;
// }

 

 

---

 

 

flattenArr

 

문제

 

다차원 배열을 입력받아 1차원 배열로 변환하여 리턴해야 합니다.

 

입력

 

인자 1 : arr

• 양의 정수 또는 배열을 요소로 갖는 다차원 배열 (입출력 예시 참고)

 

출력

• 배열을 리턴해야 합니다.

 

주의 사항

• 함수 flattenArr는 재귀함수의 형태로 작성합니다.
• Array Method flat()과 flatMap() 사용은 금지됩니다.
• 반복문(for, while) 사용이 가능합니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 입력으로 전달되는 다차원 배열이 중첩된 정도(중첩의 깊이)는 정해져 있지 않습니다.
• 빈 배열을 입력받은 경우, 빈 배열을 리턴해야 합니다.

 

입출력 예시

 

let output = flattenArr([[1], 2, [3, 4], 5]);
console.log(output); // --> [1, 2, 3, 4, 5]

output = flattenArr([[2, [[3]]], 4, [[[5]]]]);
console.log(output); // --> [2, 3, 4, 5]

 

 

나의 코드

 

function flattenArr(arr) {
  
// 1차원 배열이 될 때까지 재귀
// 요소 중 하나라도 배열일 경우 자기 자신 호출
  if (arr.length === 0) return [];
  
  const [head, ...tail] = arr;
  if(Array.isArray(head)) {
    return flattenArr([...head, ...tail]);
  }
  return [head].concat(flattenArr(tail));
}




// [0, [1], 2, [3, 4], 5]
// 앞 [0]
// 타겟 [1]
// 뒤 [2, [3, 4], 5]



// return arr.toString().split(',').map((el) => Number(el));
// 하면 끝이긴 함

// [[1], 2, [3, 4], 5]

// head: [1], tail: [2, [3, 4], 5]
// head: Array

// flattenArr([1, 2, [3, 4], 5])

// head: 1, tail: [2, [3, 4], 5]
// head: ***not Array
// return [1].concat(flattenArr([2, [3, 4], 5]))

// flattenArr([2, [3, 4], 5]) 호출

// head: 2, tail: [[3, 4], 5]
// head: ***not Array
// return [2].concat(flattenArr([[3, 4], 5]))

// flattenArr([[3, 4], 5]) 호출

// head: [3, 4], tail: [5]
// head: Array

// flattenArr(3, 4, 5)

// head: 3, tail: [4, 5]
// head: ***not Array
// return [3].concat(flattenArr([4, 5]))

// flattenArr([4, 5]) 호출

// head: 4, tail: [5]
// head: ***not Array
// return [4].concat(flattenArr([5]))

// flattenArr([5]) 호출

// head: 5, tail: []
// head: ***not Array
// return [5].concat(flattenArr([]))

// flattenArr([]) 호출

// if (arr.length === 0) return [];


// 여기서부터 거꾸로

// [5].concat(flattenArr([])) => [5].concat([]) => [5]
// [4].concat(flattenArr([5])): => [4].concat([5].concat(flattenArr([]))) => [4, 5]
// [3].concat(flattenArr([4, 5])) => [3].concat([4].concat(flattenArr([5]))) => [3, 4, 5]
// [2].concat(flattenArr([[3, 4], 5])) => [2].concat([3].concat([4].concat(flattenArr([5])))) => [2, 3, 4, 5]
// [1].concat(flattenArr([2, [3, 4], 5])) => [1].concat.[2].concat([3].concat([4].concat(flattenArr([5])))) => [1, 2, 3, 4, 5]

// 거꾸로 보면 이해는 되는데, 무의 상태에서 저 코드를 쓸 수 있을까? NO ~

 

 

레퍼런스 코드

 

function flattenArr(arr) {
  // base case
  if (arr.length === 0) {
    return [];
  }

  // recursive case
  const head = arr[0];
  const tail = arr.slice(1);
  if (Array.isArray(head)) {
    return flattenArr([...head, ...tail]);
  } else {
    return [head].concat(flattenArr(tail));
  }
}

// 다른 풀이 방법 1
// function flattenArr(arr) {
//   const result = [];
//   for (let i = 0; i < arr.length; i++) {
//     if (Array.isArray(arr[i])) {
//       const flattend = flattenArr(arr[i]);
//       result.push(...flattend);
//     } else {
//       result.push(arr[i]);
//     }
//   }
//   return result;
// }

// 다른 풀이 방법 2
// function flattenArr(arr) {
//   return arr.reduce(function (result, item) {
//     if (Array.isArray(item)) {
//       const flattened = flattenArr(item);
//       return [...result, ...flattened];
//     } else {
//       return [...result, item];
//     }
//   }, []);
// }