[프로그래머스] 오른쪽에서 왼쪽으로 n회 접은 종이의 상태 나타내기

 직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다. 먼저 오른쪽 절반을 왼쪽으로 접습니다.  다시 오른쪽 절반을 왼쪽으로 접습니다. 종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 종이에 접은 흔적이 생기게 됩니다. ∨ 모양이 생긴 부분은 점선(0)으로, ∧ 모양이 생긴 부분은 실선(1)으로 표시했습니다. 종이를 접은 횟수 n이 매개변수로 주어질 때,  종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접힌 부분의 모양을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

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

 

 

- 내가 풀어간 방법

 

 처음에 접근했던 방법은 n = 4 일 때, 아래와 같이 최종 결괏값 크기의 배열(2^n -1)을 먼저 생성하고, 전 단계로부터 이미 접혀진 모양을 받아온다. 한 번 더 접을 때마다 전 단계에서 새롭게 접힌 부분을 기준으로 양 옆에는 왼쪽으로는 ∨ 모양(0), 오른쪽으로는 ∧ 모양(1)으로 새롭게 접힌 부분이 생긴다. 접은 횟수에 따라 접힌 부분의 간격이 다르기 때문에 반복문에서 크기를 적절히 조절해야 하며, 이것이 까다롭다.

 

 

 다음으로 생각한 방법은 이전 단계의 접힌 모양이 현재 단계의 왼쪽 부분의 접힌 모양과 같음을 이용한 것이다. 따라서 접힌 부분을 세 부분, 왼쪽, 가운데, 오른쪽으로 나눈다. 가운데는 항상 가장 처음에 접은 ∨ 모양이며 오른쪽은 왼쪽과 반대의 음양각을 가지게 된다. 따라서 접었을 때 맞닿게 되는 위치에는 왼쪽 부분이 0이면 오른쪽 부분은 1, 왼쪽 부분이 1이면 오른쪽 부분은 0이 된다.

 map을 이용해서, 접은 횟수를 key값으로, 펼쳤을 때의 모양을 담은 배열을 value값으로 저장했다. n번 접은 모양을 구하기 위해서는 n-1번 접은 모양을 알아야 하기 때문에 입력값 n까지 반복문을 실행하며 map에 저장하고, 최종 결괏값을 반환한다. 입력 케이스가 여러 개인 경우 메모이제이션 역할을 할 수 있다.

 

 

import java.util.Arrays;
import java.util.HashMap;

public class Main {

	public static void main(String[] args) {
		// n result
		// 1 [0]
		// 2 [0,0,1]
		// 3 [0,0,1,0,0,1,1]

		int n = 3;
		int[] answer = solution(n);
		System.out.printf("%d번 접은 결과 : ", n);
		printArray(answer);
	}

	public static int[] solution(int n) {

		HashMap<Integer, int[]> map = new HashMap<>();
		map.put(1, new int[] { 0 });
		map.put(2, new int[] { 0, 0, 1 });

		return function(map, n);
	}

	public static int[] function(HashMap<Integer, int[]> map, int fold) {

		if (map.containsKey(fold))
			return map.get(fold);

		int nonExistFrom = 3;
		for (int i = 3; i <= fold; i++) {
			if (!map.containsKey(i)) {
				nonExistFrom = i;
				break;
			}
		}

		int[] newArray;
		for (int i = nonExistFrom; i <= fold; i++) {
			newArray = new int[(int) Math.pow(2, i) - 1];
			// 왼쪽
			for (int k = 0; k < map.get(i - 1).length; k++) {
				newArray[k] = map.get(i - 1)[k];
			}
			// 중간값
			newArray[map.get(i - 1).length] = 0;
			// 오른쪽
			for (int k = 0; k < map.get(i - 1).length; k++) {
				newArray[newArray.length - 1 - k] = 
						map.get(i - 1)[k] == 0 ? 1 : 0;
			}
			map.put(i, newArray);
		}
		return map.get(fold);
	}

	public static void printArray(int[] array) {
		for (int i = 0; i < array.length; i++) {
			System.out.printf("%2d ", array[i]);
		}
		System.out.println();
	}
}