[프로그래머스 Level 3] 종이접기 - 파이썬(Python)

문제 설명

직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다.

먼저 오른쪽 절반을 왼쪽으로 접습니다.

다시 오른쪽 절반을 왼쪽으로 접습니다.

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

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

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

 

제한조건

 

• 종이를 접는 횟수 n은 1 이상 20 이하의 자연수입니다.
• 종이를 접었다 편 후 생긴 굴곡이 ∨ 모양이면 0, ∧ 모양이면 1로 나타냅니다.
• 가장 왼쪽의 굴곡 모양부터 순서대로 배열에 담아 return 해주세요.

 

입출력 예

 

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

 

입출력 예 설명

입출력 예 #1
종이의 오른쪽 절반을 왼쪽으로 한번 접었다 펴면 아래 그림과 같이 굴곡이 생깁니다.

따라서 [0]을 return 하면 됩니다.

입출력 예 #2
문제의 예시와 같습니다.

입출력 예 #3
종이를 절반씩 세 번 접은 후 다시 펼치면 아래 그림과 같이 굴곡이 생깁니다.

따라서 [0,0,1,0,0,1,1]을 return 하면 됩니다.

 

나의 풀이

 

def solution(n):
    d=[[] for i in range(21)]
    d[1]=[0]

    for i in range(2,n+1):
        a=[]
        c=[0,1]*(2**(i-1) // 2)
        for j in range(len(c)-1):
            a.append(c[j])
            a.append(d[i-1][j])
        a.append(c[-1])
        d[i]=a
    return d[n]

종이를 접을때

n=1인 경우          [0]
n=2인 경우    [0 ,   0,    1]
n=3인 경우 [0, 0, 1, 0, 0, 1, 1]

 

n번 접는 경우에서 n+1번 접는 경우를 비교하면 2**n번 배열의 길이가 길어지는 것을 알 수 있습니다.
또한 n번 접는 경우의 배열에서 각 자리에 0,1을 번갈아가며 추가해 n+1배열을 만드는 것을 알 수 있습니다.

이를 통해 종이 접는 횟수가 n일때 배열을 만들었습니다.

 

다른 사람의 풀

 

def solution(n):
    fold = 0
    arr = [fold]

    for i in range(n - 1):
        arr = arr + [fold] + [bit ^ 1 for bit in arr[::-1]]

    return arr

n번 접은 배열에서 n+1번 접은 배열을 구하는 규칙은 기존 n번째 배열에 0을 추가하고 n번째 배열을 뒤집어 1인 경우 0으로, 0인 경우 1로 바꿉니다.
xor 연산자(^)를 사용하여 bit^1을 하였습니다. (bit가 1이면 bit^1은 0, bit가 0이면 bit^0은 1)

xor 연산자는 둘 중 하나만 1일 때 1입니다.

 

---

프로그래머스 '종이접기' : https://programmers.co.kr/learn/courses/30/lessons/62049

코딩테스트 연습 - 종이접기