[프로그래머스/Javascript] 종이 접기

알고리즘

Posted by Kyun2da on July 15, 2020

1️⃣서론

프로그래머스 level3 문제 종이 접기입니다. Javascript를 이용하여 해결하였습니다.

2️⃣문제 설명

종이 접기1 종이 접기2 종이 접기3

3️⃣풀이

종이접기 문제입니다. 이 문제는 종이를 접을때 대칭이 된다는 점을 알고 있으면 쉽게 해결할 수 있습니다. 1번 종이를 접을때는 답이 0 입니다. 2번 종이를 접을때는 답이 0 0 1 입니다. 3번 종이를 접을때는 답이 0 0 1 0 0 1 1 입니다. 4번 종이를 접을 때는 답이 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 입니다. 이를 유심히 보면 종이접기가 대칭이라는 점을 이용했을때 가운데 0을빼고 보면 양쪽 수 들이 대칭을 이루는 것을 볼 수 있습니다. 예를 들어 3번째 접을 때를 보면 0 0 1 0 0 1 1 으로 나눴을때 0 0 1의 대칭이 0 1 1 임을 알 수 있습니다. 그러므로 다음 번에 접을 수를 이전에 접었던 종이 횟수를 통해 이전에 접었던 수 + 0 + 대칭 된 수라고 정의 할 수 있습니다. 소스코드는 다음과 같습니다.

4️⃣ 내가 푼 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const solution = (n) => {
  const answer = [0];
  for (let i = 2; i <= n; i++) {
    const len = answer.length;
    answer.push(0);
    for (let j = len - 1; j >= 0; j--) {
      if (answer[j] === 1) {
        answer.push(0);
      } else {
        answer.push(1);
      }
    }
  }
  return answer;
};

5️⃣ 결론

이 문제는 관찰력이 필요했던 문제인 것 같습니다. 종이접기라는 실생활에서의 문제를 대칭성을 이용하여 양쪽의 숫자를 대칭시킨다는 의미를 파악한다면 쉽게 풀 수 있고 그렇지 못했다면 접근이 어려웠습니다. 알고리즘에서는 때론 이러한 관찰력(?), 통찰력(?)이 중요할 때가 있구나 라는 생각이 듭니다. 좀더 노력해야겠습니다.

6️⃣ 마치며..

질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️