[프로그래머스] 종이접기 알고리즘 문제 Summer/Winter Coding(2019) C# 풀이

문제 소개

직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다.

종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 아래 그림과 같이 종이에 접은 흔적이 생기게 됩니다.

아래 그림에서 ∨ 모양이 생긴 부분은 점선(0)으로, ∧ 모양이 생긴 부분은 실선(1)으로 표시했습니다.

종이를 접은 횟수 n이 매개변수로 주어질 때, 종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접힌 부분의 모양을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

입출력 예

n	result
1	[0]
2	[0,0,1]
3	[0,0,1,0,0,1,1]

나의 풀이

처음 n = 3까지의 예시로는 감이 잘 오지 않아, n = 4까지 시행하여 패턴을 찾았다.

1) 배열의 중앙값은 언제나 0이다.

2) 중앙값을 기준으로 역으로 대칭된다.

3) 이전 결과의 누적되어 결과가 나온다.

ex) n = 2일 때 [0, 0, 1]

중앙값 0 (=result[1])을 기준으로 0 (=result[0])과 1 (=result[2])는 역으로 대칭이다. (result[0]이 0이면 result[2]는 1 만약 그 반대로 result[0]이 1이면 result[2]는 0)

이전 결과에 중앙값 0을 추가하고 중앙값을 기준으로 역으로 대칭해서 값을 넣어주면 된다.

n = 1: [0] → n = 2: [0, 0, 1] → n = 3: [0, 0, 1, 0, 0, 1, 1]

코드

앞 결과값에 누적되어 결과가 나오기 때문에 재귀적함수를 사용하여 코드를 구현하였다.

using System;

public class Solution
{
    public int[] solution(int n)
    {
        int[] firstArray = new int[] { 0 };
        int[] result = solRecurcive(n, 1, firstArray);
        
        return result;
    }

우선 아래 사용할 재귀함수를 위해 n = 1일 때 결과 배열을 선언해준다.

public int[] solRecurcive(int n, int count, int[] priorAnswer)
    {
        if (count > n)
        {
            return priorAnswer;
        }

        int arrayCount = (int)Math.Pow(2, count) - 1;
        int median = arrayCount / 2;
        int[] answer = new int[arrayCount];
        Array.Copy(priorAnswer, answer, priorAnswer.Length);
        
        for (int i = 1; i < arrayCount - median; i++)
        {
            if (priorAnswer[median - i] == 0)
            {
                answer[median + i] = 1;
            }
        }
        
        return solRecurcive(n, count + 1, answer);
    }
}

재귀함수인 solRecursive()는 길이가 2^count - 1인 배열 선언 후 바로 직전의 배열을 복사한다.

그 후 중앙값을 기준으로 역으로 대칭하여 값을 대입해준다.

중앙값인 median을 기준으로 median - i가 0이면 median + i는 1, 반대로 median - i가 1이면 median + i는 0이다.

위 코드에서는 median - i가 0일 때만 median + i에 1을 대입해주었다. 그 이유는 배열을 생성할 때 따로 선언하지 않으면 0으로 초기화되기 때문이다.(너무 당연한 소리네...)

이 글을 작성할 때 확인한 것은 n = 1일 때 바로 결과를 리턴해주면 되는데 함수를 한 번 순회하는 점이 있어 조금 아쉽다.

결과

출력

n = 2, 3, 4일 때의 결과를 각각 출력해 보면 위와 같이 정상적으로 출력된다. 혹시나 위 코드를 복사해서 실행한다면 public뒤에 static을 붙여야 정상적으로 출력될 것이다.

결과 비교

다른 사람의 풀이 중 임의로 뽑은 4개의 코드를 돌려보았는데 그중 결과가 가장 괜찮은 코드와 비교하였다.

내가 작성한 코드가 속도와 메모리 측면에서 뛰어나 뿌듯하였다. ㅎㅎㅎ

BLCAN'S LAB