[ 프로그래머스 ] 종이접기 ( 자바 )

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

 

종이를 N번 접었을 때, 어떤 방향으로 접히는지 표시하는 문제 

 

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/62049

프로그래머스

 

 

 

 

핵심 

1. 문제 이해 

가장 처음에 한 번 접는 것을 제외하면, 매번 접을 때마다 중간(들)을 기준으로 양쪽에 접히는 부분이 생긴다. 

이 접히는 곳들을 left, right으로 정했다. 이 때, 오른쪽에서 왼쪽으로 접기 때문에 left는 0으로 접히고, right은 1로 접힌다. 이 특징을 이용해서 재귀함수를 만들었다. 

 

 

2. 재귀 

현재 foldCnt번 접힌 상태이며 mid까지 접은 상태일 때, 더 접어야 한다면 접고 다음 재귀를 호출한다. 

left, right을 0, 1로 표시 

 

단, 가장 처음 재귀호출 시, start와 end는 -1, 2<<n -1 로 설정해야 한다. 

그래야, ret배열에서 가장 처음 0 번째부터 값을 채울 수 있기 때문이다. 

 

 

 

 

 

추가적으로 더 궁금한 점 있으면 댓글 달아주세요! 

 

 

 

 

코드

class Solution {
  public int[] solution(int n) {
        // n번 접을 시, 2^n - 1 접힌 구간이 생긴다. 
        int totalFold = (1<<n) - 1;
        int[] ret = new int[totalFold];
        
        setFold(-1, totalFold, 1, n, ret);
        return ret;
    }
    
    /*
     * 현재까지 foldCnt번 접었으며 mid도 접혔다. 아직 N번 안 접었다면 한 번더 접는다.
     */
    static void setFold(int start ,int end, int foldCnt, int n, int[] ret) {
        if(foldCnt == n) {
            return;
        }
        
        int mid = (start + end)/2;
        int left = (start + mid)/2;
        int right = (mid + end)/2;
 
        ret[left] = 0;
        ret[right] = 1;
 
        setFold(start, mid, foldCnt+1, n, ret);
        setFold(mid, end, foldCnt+1, n, ret);
    }
}