재귀함수를 사용하여 배열에서 요소 검색

🐶·2021년 7월 4일
0

알고리즘

목록 보기
11/21

재귀함수를 배운지 벌써 3주가 지났지만...
알고리즘 문제를 풀때 DFS 관련된 무언가를 만나게 되면 계속 주눅이 들었다.

그래서 주말을 이용하여 재귀함수 코플릿 문제를 또 반복하여 풀게 되었다(벌써 3번째...!)
그 중에 기억해두고 싶은 문제가 있어서 이 문제만 따로 포스팅을 따로 하게 되었다.

배열이나 객체 요소를 탐색하는 것을 재귀형태로 탐색하면서 조건에 만족하는 무언가를 만났을 때 바로 true를 리턴하는 문제이다.

이 문제의 핵심은...?

요소들을 순서대로 탐색을 하다가, 아직 탐색하지 않은 남은 요소들이 있는데 false를 리턴하게 만들지 않는 것이었다.

그렇게 하려면 탐색 중간에 조건을 만족하는 요소를 탐색할때만 true를 반환하고 마지막까지 요소들을 탐색하도록(반복을 모두 마치도록) 해야한다.

예시 문제

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

주의사항

  • 함수 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.length === 0 || wish === '') { //빈 배열 or 빈 문자열을 입력받는 경우
    return false;
  }

  for(let gift of giftBox){ //배열의 요소 탐색!
    if(Array.isArray(gift)){ //그 요소의 타입이 배열일 경우
      if(unpackGiftbox(gift, wish)){ // ***이 부분 매우 중요*** 작은 배열을 탐색하는데 true가 나올 경우만 true 리턴. 여기서 작은배열을 탐색하여도 true를 만족하는 요소가 없을 때 false를 리턴해주면 안 됌. 그냥 조건문 밖으로 나오기만 해야 함!(다음 배열요소 탐색을 이어갈 수 있도록) 
        return true;
      }
    }
    else if(gift === wish){ //바로 wish와 같은 배열 요소를 만나면 true 리턴
      return true
    }
  }
  return false; //for문을 다 거치고 나서 true로 리턴이 되지 않은 경우는 false

}
profile
우당탕탕 개발일기📝🤖

0개의 댓글