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

문제설명

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

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

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

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

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

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

제한사항

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

해결 방법

순열의 규칙을 찾아서 풀었다.

 

문제에서 주어진 순열은 아래와 같다. 

 

n이 1일 때, 0

 

n이 2일 때, 0 0 1

 

n이 3일 때, 0 0 1 0 0 1 1

 

순열을 살펴보면 n번째 순열은 n-1번째 순열에 다가 0 이 더해지고

 

0을 기준으로 n-1번째 순열을 뒤집고 비트의 not연산을 해준 순열을 이어 붙인 순열이 된다.

 

즉, n-1번째 순열 + 0 + Not(Reverse(n-1번째 순열))와 같다.

 

JAVA

package programmers;

import java.util.*;	

public class p_62049 {
	public static int[] solution(int n) {
		String s = "0";
		
		for(int i = 1; i < n; i++) {
			String prev = s;
			String next = (new StringBuffer(s)).reverse().toString().replace("0", "2").replace("1", "3").replace("2", "1").replace("3", "0");
			s = prev + "0" + next;
		}
		
		int[] r = new int[s.length()];
		
		for(int i = 0; i < r.length; i++) {
			r[i] = s.charAt(i) - '0';
		}
		
		return r;
	}
	public static void main(String[] args) {
		int[] r = solution(4);
		for(int n : r) System.out.print(n + " ");
	}
}