Programmers) 종이접기

문제

직사각형 종이를 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 하면 됩니다.

---

설명

종이를 펼칠 때 어떤 규칙이 있는 지 확인하면 풀 수 있는 문제 였습니다.


제가 확인한 규칙은 다음과 같습니다.


1) 아래의 규칙들은 종이를 원하는 만큼 접은 상태에서, 몇번 펼치느냐에 기준을 삼는다.

2) 첫 번째 펼치는 것은 굴곡 하나만 존재하므로 무시한다.

3) 종이를 한번 펼치면 두 면이 생길 텐데, 두 면의 정 가운데 부분에 접힌 굴곡(0)이 추가된다.

4) 가운데 부분을 기준으로 왼편은 n-1 번째의 굴곡 형태이며, 오른편은 n-1 번째의 굴곡의 순서를 뒤집은 다음 0과 1을 반전시킨 값이다.

5) 따라서 n 번째(n>1) 굴곡은 다음과 같이 표시할 수 있다.

n 번째 = <n-1 번째 굴곡 형태> + 0 + <n-1 번째 굴곡 순서를 뒤집은 후 0과 1을 반전>


이제 규칙에 맞게 코드를 작성하면 됩니다.


이슈가 될 만한 부분은 이전 굴곡 순서를 뒤집은 후 0과 1을 반전시키는 것 이었는데, 저는 약간 복잡하게 접근하였습니다.


먼저 이전 굴곡 리스트값을 반전 시키는 과정을 거쳤습니다. 0이든 1이든 일단 -1을 대입한 다음, abs() 함수를 이용해 절대값을 취했습니다.


이렇게 반전된 리스트를 인덱스와 값으로 이루어진 딕셔너리로 바꾼다음, 인덱스를 기준으로 내림차순 sorting을 진행했습니다. 이렇게 굴곡 순서와 반전을 진행했습니다.


아래에 제가 푼 코드를 올려두었습니다. 참고하시기 바랍니다.

def solution(n):
    answer = [0]
    for idx in range(n-1):
        new_paper = [abs(val-1) for val in answer]
        tmp = {idx:val for idx,val in enumerate(new_paper)}
        answer.append(0)
        answer.extend([val[1] for val in sorted(tmp.items(), reverse=True)])
    return answer

좀 복잡하게 접근했는데, 좀더 효율적이고 획기적인 방법으로 푸신 분들이 계신다면 언제든 피드백 주세요~!