210615. Today I Learned(TIL) : 재귀(unpackGiftbox)

재귀함수 공부를 하면서 가장 인상깊었던 문제가 바로 이 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

우선 가장 처음 접근했던 방법은 주어진 giftBox에 wish가 포함되어 있는지 여부를 includes() 메소드로 확인하여 이 값이 true를 리턴하면 결과로 true를 리턴하게 하고, 그게 아닌 경우 giftBox를 한 단계 열어주기 위해 flat() 메소드를 사용하여 재귀호출을 하도록 코드를 작성했었다.

function unpackGiftBox(giftBox, wish) {
	if(giftBox.includes(wish) return true;
    	else if(giftBox.length === 0 || giftBox.includes(wish) === false) 
        return unpackGiftBox(giftBox.flat(), wish)
        }

하지만 이 코드의 치명적인 단점은 바로 flat() 메소드였다. 문제의 의도 자체가 flat() 메소드를 사용하지 않고 해결하는 것이 목적인 것도 있지만, flat() 메소드는 1차원 배열일 때도 자기 자신을 리턴하며 무한히 펼쳐주는 메소드이기 때문에 만약 선물상자를 다 열어도 wish와 같은 요소를 찾지 못하게 되면 재귀호출을 멈추고 false를 리턴하지 못하고 무한히 재귀호출을 반복하게 된다. 그렇게 되면 결국 'Maximum call stack size exceeded' 에러를 뱉게 된다.

그래서 레퍼런스 코드를 보고 깨달은 접근방법은 정말 단순하고 충분히 생각해낼 수 있는 접근방법이지만 내 고정관념(?) 선입견(?) 유연하지 못한 사고(?) 때문에 생각해 내지 못한 방법이었다. 그냥 for loop를 돌면서 giftBox의 선물상자를 열어주는 것이다...

function unpackGiftBox(giftBox, wish) {
	for(let i = 0; i < giftBox.length; i++) {
    	if(giftBox[i] === wish) { // giftBox의 요소와 wish가 일치하면 바로 true를 리턴
        return true;
        }
        else if(Array.isArray(giftBox[i])) { // 그렇지 않고 giftBox의 요소가 배열이라면(아직 열지 않은 선물상자)
        	const result = unpackGiftbox(giftBox[i], wish); // 재귀호출 한 결과가 true일 때
            if(result === true) return true; // 최종적으로 true를 리턴
            }
          }
          return false; // 모든 반복이 끝나고도 true를 리턴하지 못하게 되면 wish와 같은 선물을 찾지 못한 것이므로 false를 리턴
        }

재귀함수 알고리즘은 재귀 자체가 반복문의 대체이기 때문에 반복문을 쓸 이유가 없다고 생각했던 것이 이 접근방법을 생각해내지 못한 결정적인 이유였다. 재귀함수 문제라는 것이 주어지지 않았거나, 재귀함수를 사용하지 않아도 되는 다른 문제였다면 망설임 없이 for 반복으로 배열의 요소들을 순회했겠지만 재귀함수 관련 문제라는 이유만으로 for loop 관련 사고를 차단해버렸다는 것이 많이 아쉽다. 알고리즘 문제를 풀면서 나는 유연한 사고가 많이 부족하다는 생각을 지속적으로 하게 된다. 앞으로 더 다양한 문제들을 풀어나가다 보면 점점 유연한 사고가 가능해질 것이라고 생각한다. 오늘의 TIL 끝.