[Algorithm] 러시아 전통인형 마트료시카 재귀 알고리즘 Matryoshka Algorithm

 

 

 

Matryoshka는 러시아 전통 인형이다. 보통 과대 포장을 비판하기 위해서 사용되기도 하는데, 이 인형은 재귀 알고리즘에 찰떡이다. 객체로 구성된 Matryoshka 인형을 찾는 문제를 알아보자.

문제 : 

마트료시카에 대한 정보를 담은 객체를 입력받아 조건에 맞는 인형이 있는지 찾는다. 결과값은 boolean 값으로 반환하며, 반복문 사용은 금지된다. 

객체는 함수를 호출한 뒤 원본상태를 유지하는 얕은 복사를 해야 하며, 빈 객체를 입력받는 경우 false를 반환해야 한다.

객체의 size는 중첩될 수록 작아진다.

 

 

풀이 : 

재귀 알고리즘이니 base case와 recursive case로 구분한다. 먼저 탈출 조건은 주어진 자연수 N과 객체내의 size를 비교한다. N과 size가 동일한 경우 true를 반환하고 재귀 로직을 탈출한다.

객체 내에는 size와 사이즈가 작은 Matryshka 객체가 주어진다. 만약 하위 객체가 존재하고 주어진 자연수 N이 현재 객체의 size보다 작다면 재귀함수 호출이 되어야 한다.

하위 객체를 매개변수로 담은 함수를 호출하고, 만약 주어진 N보다 작은 size가 없다면 주어진 입력값에는 찾고자 하는 Matryoshka가 없기 때문에 false를 반환한다.

물론 하위 객체가 존재하지 않는 경우에도 false를 반환한다.

 

입력값

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

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

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

 

소스코드 :

function findMatryoshka(matryoshka, size) {
  // base case
  try{
    if(size === matryoshka.size) return true;
  }catch(e){

  }
  
  // recursive case
  if(matryoshka.matryoshka !== null){
    if(size < matryoshka.size)
      return findMatryoshka(matryoshka.matryoshka, size);
    else
      return false;
  }
  else{
      return false;
  }
}

 

 

 

[Algorithm] 재귀 알고리즘 배열 javascript 기본 문제 정리