[프로그래머스] '종이접기' 알고리즘 풀이 - Python

Contents

1. 문제 설명
   
   [제한사항]
   
   [입출력 예]
2. 알고리즘 분석 
   
   [나의 풀이]
   
   [Most 1 의 풀이]

---

 

문제 설명

 

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

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

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

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

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

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

 

 

 

알고리즘 분석

 

종이를 접을 때, 어떤 패턴으로 종이가 구부려지는지 확인하기 위해서 직접 종리를 접어봤다. 

 

[ 결 과 ] ( 0 : 아래로 접힘, 1 : 위로 접힘 )

• n=1, 0, 1
• n=2, 001, 3
• n=3, 0010011, 7
• n=4, 001001100011011, 15

위의 결과를 보면 패턴을 찾을 수 있다. 

 

n = 3 일 경우를 살펴보자. 

 

n = 2의 결과인 '001'이 n = 3의 결과에 포함되어 있는 것을 확인할 수 있다. 

 

n = 3가 '001' + '0' + '011' 로 이루어져 있다는 것을 알수 있다. 

 

여기서 가운데의 '0'은 종이를 접게될 경우 무조건 생기는 부분이다. 

 

그리고 뒤의 '011'은 '001'을 뒤집은 후, '0'은 '1'로 '1'은 '0'으로 변환해주었다는 것을 확인할 수 있다. 

 

n = 1에서부터 차례로 값을 구할 경우 해당하는 결과를 얻을 수 있다는 것을 알아냈다. 

 

 

• 나의 풀이

def plus(num): # 종이를 한번 더 접은 경우의 결과를 반환.
    new = '' 
    for n in num[::-1]:
        if n == '1':
            new += '0'
        else:
            new += '1'
    return num + '0' + new

def solution(n):
    answer = '0'
    for _ in range(1, n): # 종이를 n번만큼 접는다.
        answer = plus(answer)
    return list(map(int, answer)) # 결과를 요소가 int인 list로 반환한다.

 

• Most 1의 풀이

def solution(n):
    fold = 0
    arr = [fold]
    for i in range(n - 1):
        arr = arr + [fold] + [bit ^ 1 for bit in arr[::-1]] # 종이를 한번 씩 접는 결과를 arr에 담는다. 
    return arr

내가 if와 else로 구현한 '0'과 '1'을 바꾸는 부분을 'bit ^ 1'으로 간결과 하여 코드가 확연히 줄어들었다.