javascript 의 재귀함수 문제

조회수 141회
function flatten(oldArr) {
  var newArr = []
  for (var i = 0; i < oldArr.length; i++) {
    if (Array.isArray(oldArr[i])) {
      newArr = newArr.concat(flatten(oldArr[i]))
    } else {
      newArr.push(oldArr[i])
    }
  }
  return newArr;
}

// flatten([[1],[2],[3]]) // [1,2,3]
// flatten([[[[1], [[[2]]], [[[[[[[3]]]]]]]]]]) // [1,2,3]

재귀함수를 이용해서 배열의 모든값을 하나만 출력이 되도록 하는 문제입니다. 풀다가 도저히 못풀어서 문제의 해답을 보게되었는데요 코드중 for 문안에서의 작동 로직이 도저히 모르겠습니다. 해당 코드의 동작로직이 어떻게 될까요??

  • 재귀호출이 이해가 안되는 건가요? 코드 전부를 설명해달라고 하면 답변이 잘 안달릴 거에요. 특별히 어느 부분이 어려운지 찍어 보세요. 편집요청빌런 2023.1.16 18:05
  • 감사합니다. 질문을 수정했습니다. 시티젠 2023.1.16 20:55

1 답변

  • 좋아요

    3

    싫어요
    채택 취소하기

    재귀 함수를 다루는 데 있어서 가져야 되는 것이 있는데, 바로 함수에 대한 믿음입니다. 여기서 flatten 함수는 배열을 flat 하게 만들어 주는 함수입니다. 이 때 함수의 내용을 구현할 때에는 함수 안의 코드에서 등장한 flatten 함수는 올바르다고 믿어 봅시다.

    무슨 말인지 헷갈릴 수도 있을 것 같습니다. 예시를 들어 보겠습니다.

    const arr = [
      [1, [2, 3, 4], [5, [6], 7]],
      [3, 1, 4, [1]],
      5, 9,
      [2, 6, 5]
    ]
    

    우리가 arrflatten을 하고 싶다고 가정해 보겠습니다.

    • Array.isArray는 어떤 변수가 배열인지 아닌지를 알려줍니다.
      • 위에서 언급해 주신 코드는 그러면 원소가 배열인 경우에는 flatten 함수를 호출해서 newArr에 원소들을 전부 집어넣을 것이고,
      • 그렇지 않을 경우에는 원소 하나이므로 newArr에 그냥 집어넣어 줄 것입니다.

    그러면 이 flatten 함수의 구현이 맞다고 믿고, arr의 각 원소에 대해 위의 for-루프를 돌리면 어떤 일이 일어나는지 생각해 봅시다.

      [1, [2, 3, 4], [5, [6], 7]],
      // flatten 후 -> [1, 2, 3, 4, 5, 6, 7]
      [3, 1, 4, [1]],
      // flatten 후 -> [3, 1, 4, 1]
      5,
      // -> 배열이 아니므로 그대로
      9,
      // -> 배열이 아니므로 그대로
      [2, 6, 5]
      // flatten 후 -> [2, 6, 5]
    

    결국에는,

    newArr = newArr.concat([1, 2, 3, 4, 5, 6, 7])
    newArr = newArr.concat([3, 1, 4, 1])
    newArr.push(5)
    newArr.push(9)
    newArr = newArr.concat([2, 6, 5])
    

    을 하게 되고, 우리가 기대하는 [1, 2, 3, 4, 5, 6, 7, 3, 1, 4, 1, 5, 9, 2, 6, 5]가 된다는 것을 알 수 있습니다. 함수 안에 적혀 있는 flatten이 잘 실행될 거라고 믿었더니, 결과가 제대로 나오는 것을 알 수 있습니다.

    재귀 함수는 어떻게 짜나요

    재귀 함수를 분석하는 것과 일맥상통합니다. flatten이라는 재귀 함수를 처음부터 작성해야 한다고 한다면, 일단 올바른 flatten 함수가 이미 있다고 가정하고, 이걸 어떻게 활용하면 좋을지 고민해 보면 조금 더 쉽게 짤 수 있을 것입니다. 이 때 생각의 방향은 "큰 문제를 작은 문제로 쪼개서 생각한다"가 되면 더 좋겠습니다. (그렇지 않으면 function flatten(oldArr) { return flatten(oldArr) } 같은 코드를 만들 수도 있으니까요!)

    앞서 언급한 arr의 상황을 살펴봅시다. arrflatten 하려고 봅시다.

    1. 우선 이 큰 문제를 작은 문제들로 쪼개 본다면 arr의 원소 각각에 대해 flatten을 하고 생각하면 좋을 것 같아 보입니다.
    2. flatten을 하고 보니 [1, 2, 3, 4, 5, 6, 7], [3, 1, 4, 1], 5, 9, [2, 6, 5]가 나옵니다.
    3. 이제 이걸 [1, 2, 3, 4, 5, 6, 7, 3, 1, 4, 1, 5, 9, 2, 6, 5]로 바꾸는 방법을 생각해 볼 수 있겠습니다. (2)에서 (3)으로 오는 것은 처음 문제를 바로 푸려고 하는 것보다 쉬울 것입니다.

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)